A Branch-and-Cut Algorithm for Graph Coloring

Isabel Méndez-Díaz (imendezdc.uba.ar)
Paula Zabala (pzabaladc.uba.ar)

Abstract: 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.

Keywords: Graph Coloring; Integer Programming; Branch-and-Cut algorithms

Category 1: Combinatorial Optimization (Branch and Cut Algorithms )

Category 2: Combinatorial Optimization (Polyhedra )

Citation: Reporte Técnico TR 02-001 Departamento de Computación Universidad de Buenos Aires noviembre de 2002 http://www.dc.uba.ar

Download: [Compressed Postscript][PDF]

Entry Submitted: 09/02/2003
Entry Accepted: 09/02/2003
Entry Last Modified: 09/02/2003

Modify/Update this entry