🧩 Constraint Solving POTD:Graph Coloring — Colorful Constraints

[github-actions[bot]]

Category: Classic CSP · Date: 2026-04-28

Graph coloring is one of the most celebrated problems in combinatorics and constraint solving — simple to state, surprisingly deep to solve, and everywhere in practice.

---

Problem Statement

Given an undirected graph G = (V, E) and a set of k colors, assign a color to each vertex such that no two adjacent vertices share the same color. The smallest k for which this is possible is the graph's chromatic number χ(G).

Concrete instance — 5-node cycle graph (C5)

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

• With k = 2? ❌ — odd cycle, impossible.
• With k = 3? ✅ — e.g., [1→R, 2→G, 3→R, 4→G, 5→B]

Input: graph G, integer k
Output: a coloring assignment color[v] ∈ {1..k} for all v ∈ V, or UNSAT if none exists.

---

Why It Matters

• Register allocation in compilers: variables competing for CPU registers are modeled as graph nodes; edges represent conflicts; colors represent registers.
• Frequency assignment in wireless networks: channels must differ between nearby base stations to avoid interference.
• Timetabling & exam scheduling: courses sharing students cannot be scheduled in the same slot — this is exactly graph coloring on a conflict graph.
• Printed circuit board layer minimization: nets that cross need different layers.

---

Modeling Approaches

1. Constraint Programming (CP)

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

for each edge (u, v) ∈ E:
    color[u] ≠ color[v]

Symmetry breaking (crucial!): since any permutation of color labels is equivalent, add:

color[v1] = 1                        // fix first vertex
color[v2] ∈ {1, 2}                   // second vertex uses ≤ 2 colors
...                                   // lex-leader or similar

Trade-offs: CP propagation via arc consistency (AC) is strong on sparse graphs. The alldifferent global constraint doesn't apply directly here, but specialized graph-coloring global constraints (e.g., gcc) can tighten bounds.

2. Mixed-Integer Programming (MIP)

Binary variables: x[v][c] = 1 if vertex v gets color c; y[c] = 1 if color c is used.

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

Trade-offs: MIP LP relaxations give strong lower bounds on χ(G). However, the model has |V|·k + k binary variables and |E|·k constraints — it scales poorly for large dense graphs without column generation.

3. SAT Encoding

For each vertex v and color c, introduce Boolean p[v][c].

At-least-one per vertex: p[v][1] ∨ p[v][2] ∨ ... ∨ p[v][k]
At-most-one per vertex: ¬p[v][c] ∨ ¬p[v][c'] for all c ≠ c'
Conflict clauses per edge: ¬p[u][c] ∨ ¬p[v][c] for all (u,v) ∈ E, all c

Trade-offs: Modern CDCL SAT solvers handle millions of variables efficiently. Binary search on k finds χ(G). The encoding is clean but produces O(|V|·k2) clauses for the AMO constraints — commander-variable or product encodings can reduce this.

Example CP Model (MiniZinc)

int: n = 5;
int: k = 3;
int: num_edges = 5;
array[1..num_edges, 1..2] of int: edges =
  [| 1,2 | 2,3 | 3,4 | 4,5 | 5,1 |];

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

% Conflict constraints
constraint forall(e in 1..num_edges)(
  color[edges[e,1]] != color[edges[e,2]]
);

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

solve satisfy;

output [show(color)];

---

Key Techniques

1. Propagation — Arc Consistency (AC-3/AC-4)

For every edge (u, v), AC removes values from color[u]'s domain that have no support in color[v]'s domain (and vice versa). For graph coloring this is straightforward: value c is supported in color[u] iff color[v]'s domain contains some c' ≠ c.

2. Variable Ordering — DSATUR Heuristic

The DSATUR algorithm greedily colors vertices in order of saturation (number of distinct colors already used by neighbors). It produces near-optimal colorings in practice and is the basis for many exact branch-and-bound solvers. In CP search, adopting a DSATUR-inspired dynamic variable ordering (dom/deg or dom/wdeg) dramatically reduces search effort.

3. Symmetry Breaking via Lex-Leader Constraints

Color labels are interchangeable: any bijection on {1..k} yields an equivalent solution. Without symmetry breaking, the solver explores k! symmetric copies of every solution. The lex-leader approach adds:

color[first_vertex_colored_c] < c   for c = 2..k

This alone can reduce search space by orders of magnitude.

---

Challenge Corner

🔍 Can you determine χ(G) without enumerating all possible k values separately?
One approach: optimize directly — add a variable k_used and minimize it, with color[v] ≤ k_used for all v. Does this formulation propagate well? What are the trade-offs versus binary search over k?

🔍 Bonus: For planar graphs, the Four Color Theorem guarantees χ(G) ≤ 4. Can you encode planarity as a constraint and exploit this bound in a solver?

---

References

1. Rossi, van Beek & Walsh — Handbook of Constraint Programming (2006), Chapter 4: Graph Coloring as a CSP benchmark.
2. Brelaz, D. — "New methods to color the vertices of a graph," CACM 22(4), 1979. (Introduces DSATUR)
3. Trick, M. — [Constraint Programming tutorial on Graph Coloring]((mat.gsia.cmu.edu/redacted) — accessible overview with benchmark instances.
4. Gecode documentation — [Global Constraints for Graph Coloring]((www.gecode.org/redacted) — solver-level implementation details.

---

Have a solution, a question, or a different modeling angle? Share it in the replies! 👇

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

• expires on May 5, 2026, 1:11 PM UTC