Graph coloring is a well known problem from graph theory that, when
solving it with local search algorithms, is typically treated as a
series of constraint satisfaction problems: for a given number of
colors k, one has to find a feasible coloring; once such a coloring
is found, the number of colors is decreased and the local search
starts again. Here we explore the application of Iterated Local
Search to the graph coloring problem. Iterated Local Search is a
simple and powerful metaheuristic that has shown very good results for
a variety of optimization problems. In our research we investigate
different perturbation schemes and present computational results on
some hard instances from the DIMACS benchmark suite.
