Given an undirected graph G = (V, E), the vertex coloring problem (VCP) requires to assign a color to each vertex in such a way that colors on adjacent vertices are different and the number of colors used is minimized. In this paper, we propose a metaheuristic approach for VCP that performs two phases: the first phase is based on an evolutionary algorithm, whereas the second one is a postoptimization phase based on the set covering formulation of the problem. Computational results on a set of DIMACS instances show that the overall algorithm is able to produce high–quality solutions in a reasonable amount of time. For four instances, the proposed algorithm is able to improve the best–known solution while for almost all the remaining instances, it finds the best–known solution in the literature.
