🧩 Constraint Solving POTD:Problem of the Day: Graph Coloring

[github-actions[bot]]

Problem Statement

The graph coloring problem asks: given an undirected graph, assign a color to each vertex such that no two adjacent vertices share the same color, while minimizing the total number of colors used.

Concrete Instance

Consider a simple graph with 4 vertices representing four courses:

• Vertices: {Math, Physics, Chemistry, History}
• Edges (representing course conflicts):
  • Math ↔ Physics (same student might want both)
  • Math ↔ Chemistry
  • Physics ↔ Chemistry
  • Chemistry ↔ History

Question: Can you schedule these courses using 3 colors (time slots), or do you need 4?

Solution: Color 1 (Math), Color 2 (Physics, History), Color 3 (Chemistry). Yes, 3 colors suffice!

Input/Output Specification

Input: An undirected graph G = (V, E) with vertices V and edges E

Output: A mapping color: V → {1, 2, ..., k} such that for every edge (u, v) ∈ E, we have color(u) ≠ color(v), and k (the chromatic number) is minimized.

---

Why It Matters

Register Allocation in Compilers: When compiling code, a compiler must assign CPU registers to variables. Two variables that are "live" simultaneously (used in overlapping time windows) cannot share the same register—this is exactly graph coloring, where vertices are variables and edges connect variables that conflict.

Exam Scheduling: Universities must schedule exams for courses such that students taking multiple courses don't have conflicting exam times. Courses are vertices, edges connect courses with common students, and colors are exam time slots.

Frequency Assignment: Telecom networks assign radio frequencies to base stations to minimize interference. Stations that are geographically close (edges) must use different frequencies (colors).

Map Coloring: The famous four-color theorem states that any planar map can be colored with at most 4 colors. This classic result motivated much of early graph theory and constraint solving research.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Decision Variables:

• color[v] ∈ {1, 2, ..., k} for each vertex v ∈ V

Constraints:

• color[u] ≠ color[v] for all edges (u, v) ∈ E (inequality constraints)
• Optionally, alldifferent() on clique subsets to propagate more strongly

Objective: Minimize k

Trade-offs:

• Strengths: Simple to model, powerful global constraints (e.g., alldifferent) provide strong propagation
• Weaknesses: Requires iterating over edge set explicitly; less natural for large sparse graphs

Example Model (MiniZinc)

int: n = 4;  % number of vertices
int: max_colors = n;

% Define edges (example: 0-1, 0-2, 1-2, 2-3)
array[1..4, 1..2] of int: edges = [
  [1, 2], [1, 3], [2, 3], [3, 4]
];

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

% Inequality constraints for each edge
constraint forall(e in 1..4)(
  color[edges[e, 1]] != color[edges[e, 2]]
);

% Minimize the largest color used
var 1..max_colors: num_colors = max(color);
solve minimize num_colors;

output [
  "Colors: ", show(color), "
",
  "Chromatic number: ", show(num_colors), "
"
];

Approach 2: Integer Linear Programming (MIP)

Decision Variables:

• Binary variable x[v, c] ∈ {0, 1} for each vertex v and color c ∈ {1, ..., k}, where x[v, c] = 1 iff vertex v gets color c
• Auxiliary variable used[c] ∈ {0, 1} indicating whether color c is used

Constraints:

• ∑_c x[v, c] = 1 for all v (each vertex gets exactly one color)
• x[u, c] + x[v, c] ≤ 1 for all edges (u, v) and colors c (endpoints of edges don't share colors)
• used[c] ≥ x[v, c] for all v, c (color c is marked used if any vertex uses it)

Objective: Minimize ∑_c used[c]

Trade-offs:

• Strengths: General-purpose solvers (CPLEX, Gurobi); good for large instances; LP relaxation provides bounds
• Weaknesses: Larger formulation; tighter connection to polyhedral relaxations needed for quality bounds

---

Key Techniques

1. Greedy Heuristics & Degeneracy Ordering

A simple greedy algorithm colors vertices in order, assigning each vertex the smallest color not used by its neighbors. The order matters: degeneracy ordering (iteratively removing the vertex with fewest uncolored neighbors) often yields better solutions. This is a fast preprocessing step combined with search.

2. Arc Consistency & Propagation

In CP, maintaining arc consistency on inequality constraints removes impossible values early. For cliques (fully connected subgraphs), use alldifferent() constraints to propagate aggressively. Bounds consistency on max(color) tightens the domain of the chromatic number variable as colors are assigned.

3. Symmetry Breaking & Partial Coloring

Graph coloring has inherent symmetry: swapping colors does not change the solution's quality. Symmetry-breaking constraints like "color(v1) < color(v2)" for a canonical pair of vertices (e.g., highest-degree vertices) reduce the search space. Alternatively, partial coloring techniques order vertices by degree and branch on high-degree vertices first, since they constrain the problem most.

---

Challenge Corner

Can you model graph coloring as a SAT problem? Graph coloring can be encoded in Boolean satisfiability: use Boolean variables p[v, c] ("vertex v has color c") and write clauses enforcing exactly-one color per vertex and conflict-free edges. What is the clause complexity, and how does SAT solver performance compare to dedicated CP solvers on structured instances?

Extension: The list coloring variant restricts each vertex v to a subset L[v] of allowed colors. How would you handle this in each model? Can you exploit list structure to improve propagation?

---

References

1. Jensen, T. R., & Toft, B. (1995). Graph Coloring Problems. Wiley-Interscience. — Comprehensive reference on graph coloring variants and algorithms.

2. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming, ch. 7 (Graph Problems). — Excellent overview of how constraint programming tackles coloring and related graph problems.

3. Kubale, M. (Ed.). (2004). Graph Colorings. American Mathematical Society. — Advanced treatment of coloring algorithms and complexity.

4. OR-Tools Graph Coloring Guide (https://github.com/google/or-tools) — Practical examples in C++, Python, and Java using Google's constraint solver library.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 5.75 AIC · ⌖ 5.83 AIC · ⊞ 6.2K · ◷

• expires on Aug 27, 2026, 3:39 AM UTC-08:00