Graph coloring problems have been studied very intensively in the past decades and many coloring methods have been proposed in the literature. A first category of methods are based on local search (also called neighborhood search). Starting from an initial solution typically constructed using a greedy heuristic, a local search algorithm improves the current solution by considering best moves in a given neighborhood.
To escape local optima traps, local search algorithms usually incorporate dedicated mechanisms such tabu lists [1]}, [2]} or perturbation strategies [3]}, [4]}. However for very difficult instances of graph coloring, the single trajectory local search approach is not powerful enough to locate very high quality solutions mainly due to its limited diversification capacity. To overcome this difficulty, hybrid algorithms have been proposed, in particular relying on the population-based memetic framework that combines local searches and crossovers [5]}. The memetic framework has been very successful in solving several graph coloring problems [6]}, [7]}, [8]}, [9]}, [10]}. These hybrid algorithms combine the benefits of local search for intensification with a population of high-quality solutions offering diversification possibilities.
