🧩 Constraint Solving POTD:Graph Coloring — Chromatic Constraints in the Wild

[github-actions[bot]]

Category: Classic CSP · Date: 2026-03-29

---

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, using as few colors as possible.

The minimum number of colors needed is the chromatic number χ(G).

Small Concrete Instance

Consider a graph with 5 vertices representing regions on a map:

    A --- B
    |  \  |
    |   \ |
    C --- D --- E
```

Edges: `{A-B, A-C, A-D, B-D, C-D, D-E}`

**Question:** What is `χ(G)`? Can you 3-color it?

<details>
<summary>Solution hint</summary>

`χ(G) = 3`. One valid 3-coloring:
- A = Red, B = Blue, C = Blue, D = Green, E = Red
</details>

**Input:** Adjacency list, budget `k` (number of colors)  
**Output:** An assignment `color[v] ∈ {1..k}` for each vertex `v`, or "infeasible" if `k < χ(G)`

---

### Why It Matters

- **Register allocation in compilers:** Variables that are "live" at the same time cannot share a CPU register — graph coloring solves the allocation directly. Every major compiler (GCC, LLVM) uses a variant of Chaitin's algorithm.
- **Frequency assignment in wireless networks:** Radio cells that are geographically close must use different frequencies to avoid interference; this maps exactly to graph coloring.
- **Examination timetabling:** Two exams sharing a student cannot run in the same slot — the conflict graph must be properly colored by time slot.
- **Sudoku:** A 9×9 Sudoku puzzle is an instance of graph coloring on the "constraint graph" where each cell is a vertex connected to all cells in the same row, column, or box.

---

### 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]
```

**Objective (optimization):** Minimize `k = max(color[v])` or binary-search on `k`.

**Trade-offs:**
- `alldifferent` propagation is not directly applicable (pairs, not sets), but **AC-3** on `≠` constraints propagates well on sparse graphs.
- For dense graphs, propagation can become expensive — symmetry breaking is critical (see Key Techniques).
- CP excels at finding *any* feasible coloring quickly, less so at proving optimality for large instances.

---

#### Approach 2 — SAT Encoding

Introduce Boolean variables `x[v][c]` meaning "vertex `v` is assigned color `c`".

**At-least-one (ALO):** Each vertex gets a color:
```
∀ v :  x[v][1] ∨ x[v][2] ∨ ... ∨ x[v][k]
```

**At-most-one (AMO):** Each vertex gets at most one color:
```
∀ v, c1 ≠ c2 :  ¬x[v][c1] ∨ ¬x[v][c2]
```

**Conflict clauses:** Adjacent vertices differ:
```
∀ (u,v) ∈ E, ∀ c :  ¬x[u][c] ∨ ¬x[v][c]
```

**Trade-offs:**
- Clause count is `O(|V|·k²/2 + |E|·k)` — manageable for moderate `k`.
- Modern CDCL SAT solvers handle symmetry via clause learning implicitly; explicit symmetry breaking (see below) still helps.
- Binary-search on `k`: run the SAT solver for `k = Δ(G)` down to `χ(G)`, where `Δ(G)` is the maximum degree.

---

#### Approach 3 — Integer Linear Programming (ILP/MIP)

Use the **clique cover** or **column generation** formulations. A simple direct MIP:

```
x[v][c] ∈ {0,1}          # vertex v assigned color c
y[c]    ∈ {0,1}          # color c is used

∀ v :   Σ_c x[v][c] = 1
∀ (u,v)∈E, ∀ c :  x[u][c] + x[v][c] ≤ y[c]  (or ≤ 1)
Minimize Σ_c y[c]

Trade-offs:

• LP relaxation bound is often weak without cutting planes or column generation.
• Column generation (generating independent sets as columns) gives much tighter bounds and is the state-of-the-art for exact chromatic number computation.

---

Example Model (MiniZinc — CP approach)

int: n = 5;
int: k = 3;
int: m = 6;

% Edges (0-indexed)
array[1..m, 1..2] of 1..n: edges = [|
  1,2 | 1,3 | 1,4 | 2,4 | 3,4 | 4,5 |];

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

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

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

solve satisfy;

output ["color = \(color)\n"];
```

</details>

---

### Key Techniques

#### 1. Symmetry Breaking
Colors are interchangeable: any permutation of color labels yields another valid coloring. Without breaking this symmetry, a solver explores `k!` equivalent solutions.

**Standard fix:** Add *lex-leader* or *value-ordering* constraints:
- Force vertex with smallest index to use color 1.
- Enforce that new colors are introduced in order: color `c+1` is only used after color `c` appears.

```
color[first_vertex] = 1
∀ c > 1 :  ∃ v < min_vertex_using(c+1) with color[v] = c

This alone can yield orders-of-magnitude speedups.

2. DSATUR Heuristic (Variable Ordering)

DSATUR (Degree of Saturation) is the classic search heuristic for graph coloring:

• At each step, choose the uncolored vertex with the most differently-colored neighbors (saturation degree); break ties by highest degree.
• This greedy ordering often produces near-optimal colorings and is the backbone of many exact backtracking algorithms.
• In CP: implement as a first-fail heuristic on the color variable with the smallest remaining domain.

3. Bounding via Clique and Fractional Relaxations

• Lower bound: The size of any clique ω(G) ≤ χ(G). Finding maximum cliques (itself NP-hard, but fast in practice) gives a tight lower bound.
• Upper bound: Greedy coloring gives χ(G) ≤ Δ(G) + 1 (Brook's theorem: equality only for complete graphs and odd cycles).
• Fractional chromatic number χ_f(G): solvable in polynomial time via LP, gives χ_f(G) ≤ χ(G) — useful for pruning in branch-and-bound.

---

Challenge Corner

Can you encode graph coloring as a single alldifferent constraint?

Hint: Think about how to represent the constraint graph so that one global alldifferent suffices — or prove why a direct encoding is impossible for general graphs.

Bonus extensions to ponder:

• List coloring: Each vertex v has a list L(v) ⊆ {1..k} of allowed colors. How does this change the propagation?
• Robust coloring: Some edges may be added adversarially after solving. Can you find a coloring that remains valid under any single edge insertion?
• Weighted coloring: Colors have costs; minimize total cost rather than number of colors.

---

References

1. Rossi, van Beek & Walsh — Handbook of Constraint Programming (2006), Chapter 4 (Arc Consistency) and Chapter 23 (Graph Coloring). The definitive CP reference.
2. D. Brélaz, "New methods to color the vertices of a graph" (CACM 1979) — the original DSATUR paper; short and very readable.
3. Trick, M. A., "A tutorial on integer programming" + color formulation: (mat.tepper.cmu.edu/redacted)
4. Malaguti, E. & Toth, P., "A Survey on Vertex Coloring Problems" (IJOC 2010) — broad survey covering exact, heuristic, and metaheuristic approaches with computational comparisons.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 5, 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 #23548.