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}
}