Graph Coloring: Chasing the Chromatic Number with Heuristics

Coloring a graph so no edge is monochrome

A proper coloring of a graph assigns each vertex a color such that no two vertices joined by an edge share a color. The smallest number of colors that makes this possible for a given graph is its chromatic number, written χ(G). Graph coloring looks abstract but it is really a scheduling primitive in disguise: vertices are exams, tasks or radio channels, edges are conflicts, and a proper coloring is a conflict-free assignment — final exam timetabling, register allocation in compilers and wireless frequency assignment are all graph coloring in different clothes.

Why finding χ(G) exactly is hard

Deciding whether a graph can be colored with k colors is NP-complete for any k ≥ 3 — there is no known algorithm that solves it in polynomial time for all graphs, and most computer scientists believe none exists. This is why every practical coloring tool uses a heuristic: an ordering rule for which vertex to color next, plus a rule for which color to give it, that produces a good coloring quickly without any guarantee of optimality.

Greedy coloring and why order matters

The simplest heuristic visits vertices in some order and assigns each the lowest-numbered color not already used by an already-colored neighbour:

for v in vertex_order:
  used = colors of v's already-colored neighbours
  color[v] = smallest color not in used

This always terminates and always uses at most Δ+1 colors, where Δ is the graph's maximum degree — a real guaranteed bound. But the order you feed it matters enormously: a poorly chosen order can force the greedy rule to use far more colors than necessary on a graph that could have been colored with very few, and a well chosen order can hit the optimum. This is why greedy coloring alone is not one algorithm, it is a family of algorithms distinguished entirely by ordering strategy.

Welsh-Powell: order by degree

The Welsh-Powell heuristic (1967) sorts vertices by descending degree before running the greedy rule, on the reasoning that highly-connected vertices have the most constraints and should be colored first while the most color choices are still available. It is simple, fast, and noticeably better than a random or arbitrary vertex order on most real graphs, though it still has no worst-case optimality guarantee.

DSatur: order by saturation, dynamically

DSatur (Brélaz, 1979) improves on Welsh-Powell by recomputing the order as it goes: at each step it colors the uncolored vertex with the highest saturation degree — the number of distinct colors already used among its neighbours — breaking ties by degree in the remaining uncolored subgraph. This adapts to the coloring in progress rather than committing to a fixed order upfront, and it is provably optimal on several important graph families, including bipartite graphs. On general graphs it still is not guaranteed optimal, but in practice it consistently outperforms static-order greedy and Welsh-Powell, which is why it is the default heuristic in most production coloring tools today.

How close is close enough

For many real graphs, especially sparse or structured ones, DSatur lands on the true chromatic number or within one color of it. The hardest cases are dense, irregular graphs with no obvious structure to exploit, where even DSatur can land several colors above χ(G) and only an exact search (branch-and-bound, or integer programming) can confirm the true minimum — at a computational cost that grows explosively with graph size. This is the practical trade-off every coloring heuristic makes: DSatur trades a small, usually-invisible gap above the optimum for a runtime that scales to graphs with millions of vertices, where exact solvers cannot go at all.

Frequently asked questions

Try it live

Everything above runs in your browser — open Graph Coloring and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.