  The graph coloring problem is often investigated in the literature. Many
insights about many neighboring solutions with the same fitness value are
raised but as far as we know, no deep analysis of this neutrality has ever been
conducted in the literature. In this paper, we quantify the neutrality of some
hard instances of the graph coloring problem. This neutrality property has to
be detected as it impacts the search process. Indeed, local optima may belong
to plateaus that represents a barrier for local search methods. In this work,
we also aim at pointing out the interest of exploiting neutrality during the
search. Therefore, a generic local search dedicated to neutral problems, NILS,
is performed on several hard instances.
