In a previous work, we proposed a new integer programming formulation for the graph coloring problem which, to a certain extent, avoids symmetry. We studied the facet structure of the 0/1-polytope associated with it. Based on these theoretical results, we present now a Branch-and-Cut algorithm for the graph coloring problem. Our computational experiences compare favorably with the well-known exact graph coloring algorithm DSATUR.
Citation
Reporte Técnico TR 02-001 Departamento de Computación Universidad de Buenos Aires noviembre de 2002 http://www.dc.uba.ar