A Branch-and-Cut for Graph Coloring

MÉNDEZ-DÍAZ, ISABEL; ZABALA, PAULA

DISCRETE APPLIED MATHEMATICS

Elsevier Science

Lugar: Amsterdam; Año: 2006 vol. 154 p. 826 - 847

0166-218X

In this paper a Branch-and-Cut algorithm, based on a formulation previously introduced by us, is proposed for the Graph Coloring Problem. Since colors are indistinguishable in graph coloring, there may typically exist many different symmetrical colorings associated with a same number of colors. If solutions to an integer programming model of the problem exhibit that property, the Branch-and-Cut method tends to behave poorly even for small size graph coloring instances. Our model avoids, to certain extent, that bottleneck. Computational experience indicates that the results we obtain improve, in most cases, on those given by the well-known exact solution graph coloring algorithm Dsatur.