Skip to main content
Graph Coloring Facets from All-Different Systems
Lecture Notes in Computer Science
  • David Bergman, Carnegie Mellon University
  • John N. Hooker, Carnegie Mellon University
Date of Original Version
Abstract or Description

We explore the idea of obtaining valid inequalities for a 0-1 model from a constraint programming formulation of the problem. In particular, we formulate a graph coloring problem as a system of all-different constraints. By analyzing the polyhedral structure of all-diff systems, we obtain facet-defining inequalities that can be mapped to valid cuts in the classical 0-1 model of the problem. We focus on cuts corresponding to cyclic structures and show that they are stronger than known cuts. For example, when an existing separation algorithm identifies odd hole cuts, we can supply stronger cuts with no additional calculation. In addition, we generalize odd hole cuts to odd cycle cuts that are stronger than any collection of odd hole cuts.

Citation Information
David Bergman and John N. Hooker. "Graph Coloring Facets from All-Different Systems" Lecture Notes in Computer Science Vol. 7298 (2012) p. 50 - 65
Available at: