A Branch-and-Cut algorithm for Graph Coloring

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. (c) 2005 Elsevier B.V. All rights reserved.