Genetic and hybrid algorithms for graph coloring

Some genetic algorithms are considered for the graph coloring problem. As is the case for other combinatorial optimization problems, pure genetic algorithms are outperformed by neighborhood search heuristic procedures such as tabu search. Nevertheless, the authors examine the performance of several hydrid schemes that can obtain solutions of excellent quality. For some graphs, they illustrate that genetic operators can fulfill long-term strategic functions for a tabu search implementation that is chiefly founded on short-term memory strategies.