The aim of this paper is to introduce a new evolutionary formulation of the graph coloring problem, based on the interplay between orderings and colorings of vertices. The new formulation breaks symmetry in the solution space and provides opportunities for combining evolutionary and other search tehniques. Our formulation is very simple compared to previous approaches which use the relationship between a graph's chromatic number and its acyclic orientations.
We outline an initial version of a Genetic Algorithm which implements this approach to the coloring problem. We summarise the results obtained from a set of systematic experiments; they provide convincing evidence that the new ordering approach can lead to accurate genetic coloring solvers, despite the contrary popular belief.
