🧩 Constraint Solving POTD:Graph Coloring

[github-actions[bot]]

Category: Classic CSP | Date: 2026-04-17

---

Problem Statement

Graph coloring asks: given a graph G = (V, E), assign a color from a set {1, ..., k} to each vertex such that no two adjacent vertices share the same color. The chromatic number χ(G) is the minimum k for which this is possible.

Concrete Instance — The Petersen Graph (10 vertices, 15 edges)

Label the vertices 0–9. The outer pentagon connects 0–1–2–3–4–0; the inner pentagram connects 5–7–9–6–8–5; spokes connect 0–5, 1–6, 2–7, 3–8, 4–9.

Can you color it with 3 colors so that every edge separates two different colors?

Input: adjacency list (or matrix), number of colors k
Output: an assignment color: V → {1..k} satisfying all edge constraints, or UNSAT if none exists.

---

Why It Matters

• Register allocation in compilers: variables are vertices, edges represent "live at the same time" conflicts; colors are CPU registers. Minimizing colors = minimizing spills.
• Exam / course timetabling: courses sharing students must not overlap; colors are time slots. Used daily by universities worldwide.
• Frequency assignment in wireless networks: adjacent cells cannot share frequencies to avoid interference. Regulatory bodies use it to allocate spectrum.
• Printed circuit board testing and map coloring are the canonical textbook cases — the famous Four Color Theorem guarantees χ ≤ 4 for any planar map.

---

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]

Global constraint (optional):
Wrap with alldifferent over cliques to tighten propagation.

Trade-offs:

• Natural, declarative model; propagation quickly prunes infeasible color assignments
• Works well with symmetry breaking (see below)
• Scales to hundreds of vertices with good search strategies; struggles on dense graphs without decomposition

Approach 2 — Mixed-Integer Programming (MIP)

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

Constraints:

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

Trade-offs:

• Directly optimizes the number of colors (chromatic number)
• LP relaxation is weak without additional cuts (clique inequalities help enormously)
• Column generation / branch-and-price gives state-of-the-art exact solutions for large instances

Example Model — MiniZinc (CP)

int: n;                         % number of vertices
int: k;                         % number of colors
array[1..n] of var 1..k: color;

% Edge constraints — supply as a set of pairs
array[1..m, 1..2] of int: edges;
constraint forall(e in 1..m)(
  color[edges[e,1]] != color[edges[e,2]]
);

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

solve satisfy;

For the Petersen graph with k=3, MiniZinc finds a valid 3-coloring instantly.
To find χ(G), wrap in a minimize objective or iterate k from 1 upward.

---

Key Techniques

1. Symmetry Breaking

Colors are interchangeable — swapping all red/blue vertices yields another valid solution. This creates huge amounts of value symmetry. Classic fixes:

• Lex-leader constraints: enforce color[1] ≤ color[2] ≤ first-use order
• Static ordering: assign color 1 to vertex 1, color ≤ 2 to vertex 2, etc.
  color[v] ≤ 1 + Σ_{u < v, (u,v) ∈ E} 1 (cannot introduce a new color unless forced by a neighbor)

These constraints can reduce the search space by a factor of k!.

2. DSATUR Heuristic (Variable Ordering)

DSATUR (Degree of SATURation) orders vertices by the number of distinct colors already used in their neighborhood — the most constrained vertex first. Combined with backtracking, this is among the strongest complete algorithms known for moderate-sized graphs.

At each step, branch on the uncolored vertex with the highest saturation degree; break ties by degree.

3. Clique-Based Lower Bounds & Propagation

Any clique (fully-connected subgraph) requires as many colors as it has vertices: ω(G) ≤ χ(G). Finding large cliques (itself NP-hard, but approximable) gives a tight lower bound on k and generates powerful clique constraints that propagate arc consistency far more efficiently than individual edge ≠ constraints.

---

Challenge Corner

Symmetry extension: The symmetry-breaking constraint color[v] ≤ 1 + max_used_color_among_lower_index_neighbors is easy to add. Can you prove it is complete — i.e., that it never removes all solutions when a solution exists? Under what conditions might it interact badly with other constraints?

Harder extension: Graph coloring is NP-complete in general, but polynomial on perfect graphs (where χ(G) = ω(G) always holds). Given an input graph, can your solver detect perfect graph structure and exploit it to skip the combinatorial search?

---

References

1. Rossi, van Beek & Walsh (eds.) — Handbook of Constraint Programming, Chapter 2 (CSP formulations) & Chapter 4 (arc consistency). Elsevier, 2006.
2. Brélaz, D. — "New methods to color the vertices of a graph." CACM 22(4), 1979. (The DSATUR paper)
3. Mehrotra, A. & Trick, M.A. — "A column generation approach for graph coloring." INFORMS J. on Computing 8(4), 1996. (Branch-and-price for exact chromatic number)
4. MiniZinc Tutorial — [minizinc.org/doc-latest/en/modelling.html]((www.minizinc.org/redacted) — hands-on CP modeling with graph coloring worked examples.

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

• expires on Apr 24, 2026, 12:56 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 #27186.