Solve the graph coloring problem in Python

Graph coloring — assign a color to each vertex so no edge joins two of the same color, using as few colors as possible — is the model behind register allocation, exam timetabling, and frequency assignment. The default Python answers are backtracking or a greedy pass, neither of which proves the minimum. With quicopt you get the chromatic number — the provable fewest colors — in a few lines.

The naive approach

Backtracking explores color assignments until one works; greedy colors vertices in order with the first free color. Both give a valid coloring, but not necessarily the fewest colors, and backtracking blows up on hard graphs. Model it instead.

Model it as a MILP

x[v][c] gives vertex v color c; y[c] marks color c as used. Every vertex gets one color, adjacent vertices never share a used color, and we minimize colors used (with a little symmetry breaking so equivalent colorings don't multiply):

from ortools.math_opt.python import mathopt
from quicopt import Client
edges = [(0,1),(1,2),(2,3),(3,4),(4,0)]  # 5-cycle: chromatic number 3
N, K = 5, 4
model = mathopt.Model(name="graph_coloring")
x = [[model.add_binary_variable(name=f"x_{v}_{c}") for c in range(K)] for v in range(N)]
y = [model.add_binary_variable(name=f"y{c}") for c in range(K)]
for v in range(N):
    model.add_linear_constraint(sum(x[v][c] for c in range(K)) == 1)
for (u, v) in edges:
    for c in range(K):
        model.add_linear_constraint(x[u][c] + x[v][c] <= y[c])
for c in range(K - 1):
    model.add_linear_constraint(y[c] >= y[c + 1])   # symmetry break
model.add_linear_constraint(x[0][0] == 1)           # fix first vertex
model.minimize(sum(y))
print(Client("https://try.quicoptapi.pgi.fz-juelich.de").solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  3.0
├── x:          x_0_0=1, x_0_1=0, x_0_2=0, x_0_3=0, x_1_0=0, x_1_1=0, …  (24 variables)
└── solve_time: 0.0131 s

What you get

status: optimal means 3 colors is proven minimal — the chromatic number of a 5-cycle. An odd cycle can't be 2-colored, and the solver both finds a 3-coloring and proves 2 is impossible, which a greedy or backtracking pass never certifies.

The same model handles register-allocation and timetabling graphs; conflict rules are just more "not the same color" edges. K is the color budget — an upper bound on colors to try; set it to a safe value (e.g. max degree + 1, or the number of vertices) so a valid coloring always exists, since too small a K makes the model infeasible.

Next

• The problem class behind this: Mixed-integer linear (MILP)
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley, 1995.