🧩 Constraint Solving POTD:Graph Coloring

[github-actions[bot]]

Graph Coloring is a cornerstone of constraint satisfaction, with elegant models in CP, SAT, and MIP — and direct industrial relevance in register allocation, frequency assignment, and timetabling.

---

Problem Statement

Graph Coloring asks: given a graph G = (V, E) and k colors, can you assign a color to each vertex so that no two adjacent vertices share the same color?

Concrete instance (Petersen graph, k=3):

Vertices: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Edges (outer pentagon + inner pentagram + spokes):
{(0,1),(1,2),(2,3),(3,4),(4,0), (5,7),(7,9),(9,6),(6,8),(8,5), (0,5),(1,6),(2,7),(3,8),(4,9)}

Input: Graph G, integer k
Output: Assignment color: V → {1..k} such that ∀(u,v) ∈ E: color(u) ≠ color(v), or UNSAT if impossible.

The chromatic number χ(G) is the minimum k for which a valid coloring exists.

---

Why It Matters

• Compiler register allocation: Variables correspond to vertices; edges represent live-range conflicts. Coloring with k = number of registers determines whether spilling is needed.
• Radio frequency assignment: Transmitters that interfere must use different frequencies — directly a graph coloring instance.
• Examination timetabling: Courses sharing students conflict; time slots are colors.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision variables: color[v] ∈ {1..k} for each vertex v ∈ V

Constraints:

∀ (u, v) ∈ E:  color[u] ≠ color[v]

Symmetry breaking (crucial for efficiency):

color[v*] = 1                          // fix one vertex to color 1
∀ v: color[v] ≤ 1 + max(color[u] for u < v in BFS order)

Trade-offs:

• Very natural model; alldifferent on clique subsets strengthens propagation.
• Arc consistency on ≠ constraints is cheap but propagates weakly on sparse graphs.
• Works well with VSIDS/dom-over-wdeg variable ordering.

Approach 2: SAT Encoding

Boolean variables: x[v][c] = true iff vertex v gets color c

At-least-one per vertex:

∀ v:  x[v][1] ∨ x[v][2] ∨ ... ∨ x[v][k]

At-most-one per vertex (pairwise or commander encoding):

∀ v, c1 ≠ c2:  ¬x[v][c1] ∨ ¬x[v][c2]

Edge constraints:

∀ (u,v) ∈ E, ∀ c:  ¬x[u][c] ∨ ¬x[v][c]

Trade-offs:

• SAT solvers (CDCL) excel at infeasibility proofs; competitive on large sparse graphs.
• Clause count is O(|V|·k2 + |E|·k) — manageable for moderate k.
• Symmetry breaking via lex-leader constraints helps but adds clauses.

Approach 3: MIP Formulation

Variables: x[v][c] ∈ {0,1}, w[c] ∈ {0,1} (is color c used?)

Objective: minimize ∑_c w[c] (find chromatic number)

Constraints:

∀ v:           ∑_c x[v][c] = 1
∀ (u,v) ∈ E, ∀c:  x[u][c] + x[v][c] ≤ w[c]
∀ c:           w[c] ≤ w[c-1]           // symmetry breaking

Trade-offs:

• Natural for optimization (minimizing k); LP relaxation provides lower bounds.
• Column generation (independent set formulation) scales to larger instances.

Example Model (MiniZinc)

int: n = 10;  % vertices
int: k = 3;   % colors to try
set of int: V = 1..n;
array[1..15, 1..2] of int: edges = [|
  1,2 | 2,3 | 3,4 | 4,5 | 5,1 |   % outer pentagon
  1,6 | 2,7 | 3,8 | 4,9 | 5,10|   % spokes
  6,8 | 8,10| 10,7| 7,9 | 9,6 |]; % inner pentagram

array[V] of var 1..k: color;

% No two adjacent vertices share a color
constraint forall(e in 1..15)(
  color[edges[e,1]] != color[edges[e,2]]
);

% Symmetry breaking: first vertex gets color 1
constraint color[1] = 1;

solve satisfy;
output ["color = \(color)\n"];

---

Key Techniques

1. Clique-based propagation
Identify maximal cliques (e.g., via greedy or Bron-Kerbosch). An alldifferent constraint over a clique of size q immediately establishes a lower bound χ(G) ≥ q and enforces stronger arc consistency than pairwise ≠.

2. DSATUR heuristic (variable ordering)
At each search node, branch on the vertex with the highest saturation degree — the number of distinct colors already used by its neighbors. DSATUR often finds optimal colorings quickly and makes an excellent value-ordering companion (smallest unused color first).

3. Symmetry breaking via canonical forms
Colors are inherently symmetric (swapping all 1s and 2s gives another valid coloring). Breaking this symmetry with lex-leader constraints or the first-fail color assignment rule (color[v] ≤ 1 + max used color so far) can reduce search by a factor of k!.

---

Challenge Corner

Can you do better than pairwise ≠ propagation?
The Grundy number of a graph gives an upper bound on χ(G) from a greedy coloring. Can you design a global constraint graph_color(color, edges, k) whose propagator computes tighter bounds using fractional relaxations or semidefinite programming (Lovász theta function θ(G))? How would you integrate such a bound into a branch-and-bound CP solver?

---

References

1. Rossi, van Beek & Walsh — Handbook of Constraint Programming (2006), Chapter 2 (CSP fundamentals) and Chapter 10 (graph problems).
2. Méndez-Díaz & Zabala — "A Branch-and-Cut Algorithm for Graph Coloring" (2006), Discrete Applied Mathematics — state-of-the-art MIP approach.
3. Trick's Graph Coloring Instances — (mat.tepper.cmu.edu/redacted) — standard benchmark suite.
4. Hebrard & Katsirelos — "Clause Learning and New Bounds for Graph Coloring" (CP 2018) — modern SAT/CP hybrid approach with clause learning.

Generated by Constraint Solving — Problem of the Day · ● 156.4K · ◷

• expires on Apr 26, 2026, 12:54 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #27344.