TR05-03 (2005) – An Ordering-Based Genetic Approach to Graph Coloring

Cornelius Croitoru, Ovidiu Gheorghies, Adriana Gheorghies

We introduce a new evolutionary formulation of the graphcoloring problem, based on the interplay between orderings and coloringsof vertices. The new formulation aims at breaking the symmetry inthe solution space and provides opportunities for combining evolutionaryand other search techniques. Our formulation is very simple comparedto previous approaches which use the relationship between a graph’schromatic number and its acyclic orientations. We have experimentedon graphs from the DIMACS Computational Challenge. The results provideevidence that the ordering approach can be used to obtain accuratecolorings. We also give a general property which accounts for the computationaldifficulty of all approaches that attempt to iteratively reduce the number ofcolors in a coloring.

Bibtex

@TechReport{obgagc,
author = " Cornelius Croitoru and Ovidiu Gheorghie{c s} and Adriana Gheorghie{c s}",
title = " An Ordering-Based Genetic Approach to Graph Coloring",
institution = "``Al.I.Cuza'' University of Ia{c s}i, 
                 Faculty of Computer Science",
year = "2005",
number = "TR 05-03",
note = "URL:http://www.infoiasi.ro/~tr/tr.pl.cgi"
}