🧩 Constraint Solving POTD:Graph Coloring

[github-actions[bot]]

🎨 Problem of the Day: Graph Coloring

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 5-vertex "wheel" graph (a central hub connected to a 4-cycle):

Vertices: {0, 1, 2, 3, 4}
Edges:    {0-1, 0-2, 0-3, 0-4,   ← hub connects to all
           1-2, 2-3, 3-4, 4-1}   ← outer cycle

Question: What is χ(G) for this graph, and what is a valid coloring?

Answer: χ(G) = 3. One valid 3-coloring: {0→R, 1→G, 2→B, 3→G, 4→B}.

Input / Output

• Input: A graph G = (V, E), optionally an upper bound k on colors
• Output: A valid assignment color: V → {1..k}, or proof that none exists

---

Why It Matters

Register allocation in compilers: Variables that are "live" at the same time cannot share a CPU register — exactly the graph coloring problem on the interference graph. Modern compilers (LLVM, GCC) rely on coloring heuristics for this.

Timetabling and scheduling: Exams that share students cannot be scheduled in the same slot — model each exam as a vertex, conflicts as edges, and time slots as colors. Universities schedule thousands of exams this way.

Frequency assignment in wireless networks: Neighboring cells that would interfere must use different frequency channels. Cellular network planning is a weighted graph coloring problem at its core.

---

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]     // adjacency
color[0] = 1                            // symmetry breaking: fix first vertex
color[u] ≤ max(color[1..u-1]) + 1      // Lex-leader / DSATUR ordering

Objective: Minimize k = max(color[v] : v ∈ V)

Trade-offs: CP excels here because the alldifferent-like propagation and arc-consistency on ≠ constraints prune the search space aggressively. Adding symmetry-breaking constraints (e.g., color[u] ≤ color[v] + 1 in vertex-order) drastically reduces the search tree.

---

Approach 2 — Integer Linear Programming (MIP/ILP)

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

Constraints:

∀ v:            Σ_c x[v][c] = 1              // exactly one color per vertex
∀ (u,v) ∈ E, ∀ c:  x[u][c] + x[v][c] ≤ 1   // no shared color on edge
∀ v, c:         x[v][c] ≤ y[c]              // color c used only if y[c]=1

Objective: Minimize Σ_c y[c]

Trade-offs: The LP relaxation is weak (fractional solutions proliferate), so MIP solvers need many branch-and-bound nodes. However, adding clique inequalities — for each clique Q, Σ_{v∈Q} x[v][c] ≤ 1 — tightens the relaxation significantly and is standard practice.

Example Model (MiniZinc)

int: n;         % number of vertices
int: k;         % maximum colors to try
array[1..n, 1..n] of 0..1: adj;   % adjacency matrix

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

% Adjacency constraint
constraint forall(u in 1..n, v in u+1..n where adj[u,v] = 1)(
    color[u] != color[v]
);

% Symmetry breaking: colors appear in order
constraint forall(v in 2..n)(
    color[v] <= max(color[1..v-1]) + 1
);

% Minimize number of colors used
var 1..k: num_colors = max(color);
solve minimize num_colors;

Run with increasing k starting from a lower bound (e.g., clique number ω(G)) until satisfiable.

---

Key Techniques

1. DSATUR Heuristic (Greedy + Bounding)

DSATUR (Degree of SATURation) greedily colors vertices in order of saturation — the number of distinct colors already used by their neighbors. It often produces near-optimal colorings and is commonly used to find a good upper bound before exact search.

2. Symmetry Breaking

Without symmetry breaking, any permutation of a valid k-coloring is another valid coloring — yielding k! symmetric solutions. Standard fixes:

• Static: Fix color[0] = 1, enforce color[v] ≤ max(color[0..v-1]) + 1
• Dynamic: Lex-leader constraints (stronger but expensive)

These alone can reduce search time by orders of magnitude.

3. Clique-Based Lower Bounds

The chromatic number χ(G) ≥ ω(G) (clique number). Finding a large clique (even heuristically via greedy clique algorithms) gives a tight lower bound for branch-and-bound. Combined with fractional relaxation bounds, solvers can prune entire subtrees without branching.

---

Challenge Corner

Can you encode graph coloring as a SAT instance?

Given a graph G and a fixed k:

• Introduce Boolean variables x[v][c] for each vertex–color pair
• Add at-least-one and at-most-one clauses per vertex, and conflict clauses per edge
• Feed to any SAT solver (e.g., MiniSat, CaDiCaL)

Extensions to explore:

• List coloring: each vertex has its own allowed set of colors — how does this change the model?
• Precoloring extension: some vertices are already colored (fixed) — how do you integrate this?
• Edge coloring: color the edges so incident edges get different colors — what's the relationship to vertex coloring on the line graph?

---

References

1. Rossi, van Beek & Walsh — Handbook of Constraint Programming (2006), Ch. 2–4: foundational CP modeling and propagation.
2. Brélaz, D. — New Methods to Color the Vertices of a Graph (CACM 1979): the original DSATUR paper.
3. Méndez-Díaz & Zabala — A Branch-and-Cut Algorithm for Graph Coloring (Discrete Applied Mathematics 2006): state-of-the-art exact MIP approach.
4. OR-Tools Graph Coloring Tutorial — [developers.google.com/optimization]((developers.google.com/redacted) practical CP-SAT implementation walkthrough.

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

• expires on May 23, 2026, 11:43 AM 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 #32799.