🧩 Constraint Solving POTD:Graph Coloring — Color Vertices, Color the World

[github-actions[bot]]

Category: Classic CSP | Date: 2026-05-13

---

Problem Statement

Given an undirected graph G = (V, E), assign a color to each vertex such that no two adjacent vertices share the same color. The goal is to minimize the number of colors used — this minimum is called the chromatic number χ(G).

Small Concrete Instance

Consider a graph with 5 vertices and 6 edges (the cycle C5):

Vertices: {1, 2, 3, 4, 5}
Edges:    {(1,2), (2,3), (3,4), (4,5), (5,1)}

Can you 2-color it? Try it — you'll find you need 3 colors (odd cycles require 3). A valid 3-coloring: {1→R, 2→G, 3→R, 4→G, 5→B}.

Input: Graph G = (V, E), maximum colors k
Output: Assignment color: V → {1..k} satisfying all edge constraints, or UNSAT if impossible

---

Why It Matters

• Register allocation in compilers: variables are vertices; two variables that are "live" at the same time share an edge. Minimizing colors = minimizing CPU registers needed.
• Exam/frequency scheduling: schedule exams (or assign radio frequencies) so that conflicting exams (students in common) or interfering transmitters never share a time slot/frequency.
• Map coloring: the famous Four Color Theorem guarantees every planar map is 4-colorable — used in cartography and network topology planning.

---

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 (colors are interchangeable — permuting them yields equivalent solutions):

color[v*] = 1                        // fix one vertex to color 1
∀ v: color[v] ≤ 1 + max{color[u] : u < v, (u,v) ∉ E}  // DSATUR-style ordering

Trade-offs: Very natural encoding; ≠ constraints propagate well via arc-consistency (AC-3). Global alldifferent is not applicable here (we want conflicts, not uniqueness). The model scales modestly; for k-colorability checking, binary CSP suffices.

---

Approach 2 — Integer Programming (MIP/ILP)

Decision variables: x[v,c] ∈ {0,1} — 1 if vertex v gets color c; y[c] ∈ {0,1} — 1 if color c is used

Constraints:

∀ v:         Σ_c x[v,c] = 1              // exactly one color per vertex
∀ (u,v)∈E, c: x[u,c] + x[v,c] ≤ 1       // adjacent vertices differ
∀ v, c:      x[v,c] ≤ y[c]              // color used if assigned

Objective: minimize Σ_c y[c]

Trade-offs: LP relaxation gives useful lower bounds; branch-and-bound can prove optimality. However, the model has O(|V|·k) binary variables and is sensitive to symmetry. Column-generation and clique-based lower bounds (from maximum clique ω(G) ≤ χ(G)) significantly tighten the formulation.

---

Example Model (MiniZinc — CP approach)

int: n = 5;          % number of vertices
int: k = 3;          % number of colors
set of int: V = 1..n;
set of int: C = 1..k;

% Edges as pairs
array[1..6, 1..2] of int: edges = 
  [| 1,2 | 2,3 | 3,4 | 4,5 | 5,1 | 1,3 |];

array[V] of var C: color;

% No two adjacent vertices share a color
constraint forall(e in 1..6)(
  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. DSATUR Heuristic (Degree of SATURation)

At each step, color the vertex with the highest number of distinct colors already used among its neighbors (saturation degree). Ties broken by degree. This greedy heuristic often finds near-optimal colorings and is the basis for excellent branching heuristics in exact solvers.

2. Clique-Based Lower Bounds

The chromatic number satisfies χ(G) ≥ ω(G) (maximum clique size). Finding a large clique (even via heuristic max-clique solvers) gives tight lower bounds and can seed the search. Combined with the fractional chromatic number from LP relaxations, this dramatically prunes the search tree.

3. Symmetry Breaking & Value Ordering

Colors are interchangeable — any permutation of colors in a valid solution yields another valid solution. This creates massive symmetry. Breaking it (e.g., with the first-fit ordering: vertex v may only receive color c if some earlier vertex already uses colors 1..c-1) can reduce the search space by a factor of k!.

---

Challenge Corner

💡 Think about this:

The decision version of graph coloring (k-colorability for k ≥ 3) is NP-complete — yet it's solved routinely in practice for real compiler register allocation (graphs of thousands of nodes, k = 16–32).

Why does register allocation remain tractable in practice? What structural property of "interference graphs" arising from programs makes them easier to color than arbitrary graphs? Can you exploit this structure in your CP model?

Bonus: Can you model the list coloring variant, where each vertex v has its own allowed set L(v) ⊆ {1..k}, with minimal changes to the CP model above?

---

References

1. Rossi, van Beek & Walsh (eds.) — Handbook of Constraint Programming (2006), Chapter 2 (CSP basics) and Chapter 13 (graph coloring case study).
2. Brelaz, D. — ["New methods to color the vertices of a graph"]((dl.acm.org/redacted), CACM 22(4), 1979. (The DSATUR algorithm.)
3. Galinier & Hao — ["Hybrid evolutionary algorithms for graph coloring"]((link.springer.com/redacted), Journal of Combinatorial Optimization, 1999. (Local search approaches.)
4. MiniZinc documentation — [minizinc.org]((www.minizinc.org/redacted) — practical CP modeling reference with graph coloring examples.

Generated by Constraint Solving — Problem of the Day · ● 2M · ◷

• expires on May 20, 2026, 12:09 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 #32108.