An Ordering-Based Genetic Approach to Graph Coloring.

Published in Volume XV, 2005, pages 93-109

Authors: Cornelius CROITORU, Ovidiu GHEORGHIES, Adriana GHEORGHIES

Abstract

We introduce a new evolutionary formulation of the graph coloring
problem, based on the interplay between orderings and colorings of vertices.
The new formulation aims at breaking the symmetry in the solution
space and provides opportunities for combining evolutionary and other
search techniques. Our formulation is very simple
compared to previous approaches which use the relationship between a graph’s chromatic
number and its acyclic orientations. We have experimented on
graphs from the DIMACS Computational Challenge. The results
provide evidence that the ordering approach can be used to obtain
accurate colorings. We also give a general property which accounts for
the computational difficulty of all approaches that attempt to iteratively
reduce the number of colors in a coloring.

Bibtex

@article{sacscuza:croitoru2005aogatgc,
  title={An Ordering-Based Genetic Approach to Graph Coloring.},
  author={Cornelius CROITORU and Ovidiu GHEORGHIES and Adriana GHEORGHIES},
  journal={Scientific Annals of Computer Science},
  volume={15},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2005},
  pages={93--109},
  publisher={``A.I. Cuza'' University Press}
}