A Branch-and-Cut algorithm for graph coloring

A blast from the past! In this session, I plan to return to the graph coloring topic from the column generation series. More specifically, I would like to review a more “traditional” approach that involves skillfully introducing and managing the additional valid constraints, as opposed to switching to a completely different model.

A Branch-and-Cut algorithm for graph coloring

Isabel Méndez-Díaz, and Paula Zabala

Discrete Applied Mathematics, Jul 2006

IV ALIO/EURO Workshop on Applied Combinatorial Optimization

Abs HTML

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.

Relevant papers