Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs

We present in this article an evolutionary procedure for solving general optimization problems. The procedure combines efficiently the mechanism of a simple descent method and of genetic algorithms. In order to explore the solution space properly, periods of optimization are interspersed with phases of interaction and diversification. An adaptation of this search principle to coloring problems in graphs is discussed. More precisely, given a graphG, we are interested in finding the largest induced subgraph ofG that can be colored with a fixed numberq of colors. Whenq is larger or equal to the chromatic number ofG, then the problem amounts to finding an ordinary coloring of the vertices ofG.