Let G = ( V , E ) an undirected graph, V corresponds to the set of vertices and E corresponds to the set of edges, we focus on the graph coloring problem (GCP), which consist to associate a color to each vertex so that two vertices connected do not possess the same color. In this paper we propose a new hybrid genetic algorithm based on a local search heuristic called DBG to give approximate values of χ ( G ) for GCP. The proposed algorithm is evaluated on the DIMACS benchmarks and numerical results show that the proposed approach achieves highly competitive results, compared with best existing algorithms.
展开▼
