Graph Coloring, in depth: bounds, greedy orderings, DSATUR, exact backtracking, and how compilers and schedulers use it

Definitions and what makes it hard

A proper k-colouring of an undirected graph G = (V, E) is a function c from vertices to {0, 1, ..., k-1} such that c(u) differs from c(v) for every edge (u, v). Each colour class is an independent set: a set of vertices with no edges among them. So a k-colouring is a partition of the vertices into k independent sets. The chromatic number χ(G) is the smallest k for which a proper k-colouring exists.

Deciding whether χ(G) is at most 2 is easy: a graph is 2-colourable exactly when it is bipartite, which a breadth-first search checks in linear time by colouring alternate layers and looking for an edge inside a layer (see BFS and DFS, in depth). Deciding whether χ(G) is at most 3 is NP-complete, and even approximating χ within a factor of n to the power 1 minus epsilon is NP-hard for general graphs. So the engineering questions are which heuristic to use, how close it got, and when exact search is worth paying for.

Bounds: knowing when you are done

Bounds tell you when a heuristic answer is already optimal and when searching further could pay.

• Clique lower bound. If the graph contains a clique of size ω (ω vertices all adjacent to each other), every one of them needs a different colour, so χ is at least ω. A colouring that uses ω colours is therefore optimal. Finding the largest clique is itself hard, but any clique you find gives a valid lower bound.
• Degree upper bound. Greedy colouring never needs more than Δ + 1 colours, where Δ is the maximum degree, because a vertex has at most Δ neighbours and so at most Δ forbidden colours. Brooks' theorem tightens this to Δ for connected graphs that are neither complete graphs nor odd cycles.
• Degeneracy upper bound. If every subgraph has a vertex of degree at most d (the graph is d-degenerate), colouring in smallest-last order needs at most d + 1 colours. Sparse real-world graphs often have degeneracy far below their maximum degree, so this bound is usually much better than Δ + 1.
• Gaps can be large. χ can exceed ω by an arbitrary amount: there are triangle-free graphs with any chromatic number you like. The Petersen graph, for example, has no triangle (ω = 2) but needs 3 colours. So a lower bound that does not match your answer does not prove your answer is bad.

Greedy colouring and why order matters

The greedy algorithm visits vertices in some order and gives each one the smallest colour not used by an already-coloured neighbour. It is linear in the size of the graph and always produces a proper colouring. The problem is that the number of colours depends heavily on the order.

def greedy(adj, order):
    color = {}
    for v in order:
        used = {color[u] for u in adj[v] if u in color}
        c = 0
        while c in used:
            c += 1
        color[v] = c
    return color

def dsatur(adj):
    color, sat = {}, {v: set() for v in adj}
    while len(color) < len(adj):
        v = max((u for u in adj if u not in color),
                key=lambda u: (len(sat[u]), len(adj[u]), -u))
        c = 0
        while c in sat[v]:
            c += 1
        color[v] = c
        for u in adj[v]:
            sat[u].add(c)
    return color

The crown graph shows how bad an order can be. Take two sides a_0 ... a_(n-1) and b_0 ... b_(n-1), and join a_i to b_j whenever i differs from j. The graph is bipartite, so two colours suffice. But visit the vertices interleaved, a_0, b_0, a_1, b_1, and so on: a_1 and b_1 each have one coloured neighbour with colour 0 and take colour 1; a_2 and b_2 see colours 0 and 1 and take colour 2; and the pattern continues until greedy has used n colours.

def crown(n):
    # vertices a_i = 2i, b_i = 2i+1; a_i ~ b_j iff i != j
    adj = {v: set() for v in range(2 * n)}
    for i in range(n):
        for j in range(n):
            if i != j:
                adj[2*i].add(2*j+1); adj[2*j+1].add(2*i)
    return adj

for n in (4, 6):
    g = crown(n)
    bad = greedy(g, range(2*n))
    good = greedy(g, [v for v in range(2*n) if v % 2 == 0] + [v for v in range(2*n) if v % 2])
    print(n, "interleaved", len(set(bad.values())), "sides", len(set(good.values())),
          "dsatur", len(set(dsatur(g).values())))

# Output:
# 4 interleaved 4 sides 2 dsatur 2
# 6 interleaved 6 sides 2 dsatur 2

Ordering by side recovers the optimum, and so does DSATUR without being told anything about the structure. Every graph has some order for which greedy is optimal, so the whole game is choosing a good order cheaply. Three standard choices: largest-first (descending degree), smallest-last (repeatedly remove a minimum-degree vertex, then colour in reverse removal order, which achieves the degeneracy bound), and DSATUR, which picks the order dynamically. The broader theory of when local choices are globally right is in Greedy Algorithms, in depth.

DSATUR: choose the most constrained vertex next

DSATUR, from Brélaz (1979), defines the saturation of an uncoloured vertex as the number of distinct colours among its coloured neighbours. At each step it colours the vertex with the highest saturation, breaking ties by degree, and gives it the smallest free colour. As in constraint solving, the most constrained variable goes first, while it still has options.

In the code above the tie-break key is (saturation, degree, minus vertex id), so ties among equal vertices go to the smallest id and runs are deterministic. DSATUR is exact on bipartite graphs and is a strong default in general. The simple implementation shown scans all uncoloured vertices each step, which is O(n squared); a bucket queue keyed on saturation makes it close to O((n + m) log n), which you need beyond tens of thousands of vertices.

Exact colouring with backtracking

When the instance is small or the answer matters a lot, search for a proper colouring with at most k colours, and lower k until it fails. The search below orders vertices by descending degree and tries each permitted colour.

def k_colorable(adj, k):
    order = sorted(adj, key=lambda v: -len(adj[v]))
    color = {}
    def place(i):
        if i == len(order):
            return True
        v = order[i]
        used = {color[u] for u in adj[v] if u in color}
        top = max(color.values(), default=-1)
        for c in range(min(k, top + 2)):   # symmetry break: at most one new colour
            if c not in used:
                color[v] = c
                if place(i + 1):
                    return True
                del color[v]
        return False
    return dict(color) if place(0) else None

The line range(min(k, top + 2)) is the important optimisation. Colour names are interchangeable, so any colouring can be renamed so that colours first appear in order 0, 1, 2 and so on. Allowing a vertex to use at most one colour beyond the highest already used removes all those renamed duplicates, which cuts the search by up to a factor of k factorial. Without it, proving that a graph is not 3-colourable explores every relabelling of every partial colouring. The general pattern of choose, explore, unchoose and prune is covered in Backtracking, in depth.

Run on the Petersen graph, greedy in natural order and DSATUR both use 3 colours, k_colorable(P, 2) returns None, and k_colorable(P, 3) returns a colouring, which proves χ = 3. For larger exact problems, encode colouring as SAT (one boolean per vertex-colour pair, clauses for each vertex having a colour and each edge forbidding equal colours) or as an integer program, and let a solver do the search; the backtracking version is for understanding and for small instances.

Worked example: exam timetabling

Seven courses must each get one exam slot, and no student may have two exams in the same slot. Eight students take these combinations: {ALG, DB, ML}, {ML, STAT}, {DB, OS}, {NET, SEC, OS}, {ALG, SEC}, {ML, NET}, {STAT, OS}, {DB, STAT}. Build the conflict graph by adding an edge between every pair of courses that some student takes together. That gives 12 edges; DB, ML and OS have degree 4 and the rest have degree 3.

DSATUR starts with every saturation at 0 and picks the highest-degree vertex with the smallest id, DB, giving it colour 0. Its result is DB 0, SEC 0, ML 1, OS 1, ALG 2, NET 2, STAT 2: three slots. Greedy in alphabetical order also finds three: ALG 0, DB 1, ML 2, NET 0, OS 2, SEC 1, STAT 0. Is three optimal? ALG, DB and ML form a triangle (the first student takes all three), so ω is at least 3 and χ is at least 3. The clique bound matches, so we are done without any search. The exact test confirms it: k_colorable(E, 2) returns None and k_colorable(E, 3) returns the same colouring DSATUR found.

Real timetables add room capacity, daily limits and spacing; colour first for feasibility, then improve with local search that keeps the colouring proper.

Register allocation: colouring in compilers

The best-known industrial use is register allocation. A compiler computes which variables are live at the same time, builds an interference graph with an edge between any two that are simultaneously live, and tries to colour it with k colours, where k is the number of machine registers. A proper colouring is a register assignment.

Chaitin's allocator and Briggs' refinement use a simplify-and-select scheme. Any vertex with degree less than k can always be coloured later, whatever its neighbours get, so it is removed and pushed on a stack; removing it may lower other degrees and let them be removed too. If every remaining vertex has degree k or more, one is chosen as a spill candidate (kept in memory instead of a register) based on estimated cost. Vertices are then popped and given colours. Briggs' optimistic version only spills when a popped vertex really has no free colour. Coalescing merges vertices joined by copies so the copy disappears; done aggressively it makes the graph harder to colour, hence conservative coalescing rules.

A useful fact for compiler writers: when the program is in strict SSA form, the interference graph is chordal, and chordal graphs can be coloured optimally in polynomial time using a perfect elimination order. Several allocators exploit this by spilling first until register pressure fits and then colouring exactly.

Other uses and the parallel case

• Frequency and channel assignment: transmitters within interference range must use different channels.
• Parallel scheduling: tasks that touch shared data conflict; each colour class is a set of tasks that can run concurrently without locks, and the number of colours is the number of sequential phases.
• Sparse derivative computation: colouring the columns of a sparse Jacobian so that columns in one group share no nonzero row lets one finite difference or forward-mode pass recover a whole group at once.
• Parallel colouring itself: greedy is inherently sequential. Algorithms in the Jones-Plassmann style give each vertex a random priority and, in each round, colour every vertex whose priority beats all its uncoloured neighbours, which works well on GPUs and many-core CPUs at the cost of a few extra colours.

If the conflicts are directed precedence constraints rather than mutual exclusion, you need ordering, not colouring; see Topological Sort, in depth.

Failure modes and trade-offs

• Trusting one heuristic run. Greedy results vary with order. Run a few orderings, keep the best, and compare against the clique lower bound to know how much room is left.
• Non-deterministic ties. Iterating over a hash set gives different colourings across runs or language versions. Fix the tie-break explicitly.
• Exact search without a time limit. Backtracking can run for hours on a few hundred vertices. Set a time or node budget and fall back to the best heuristic result.
• Modelling the wrong graph. Missing a conflict produces an invalid schedule; adding spurious conflicts costs extra colours. Generate edges from the source data and validate every colouring by checking every edge.
• Ignoring side constraints. Capacities, preferences and fixed pre-assignments break pure colouring. Pre-colour fixed vertices first, then colour the rest, and treat soft constraints in a later improvement phase.

What to do next

1. Run the greedy, DSATUR and k_colorable functions on the crown graph and the exam example, and reproduce the printed results.
2. Add a validator that checks every edge and call it after every colouring your code produces.
3. Implement smallest-last ordering and compare its colour count with DSATUR on a large sparse graph from your own domain.
4. Write a function that finds a clique greedily, and report the gap between the clique size and your best colouring.
5. Encode a small instance as SAT and compare solver time against the backtracking search.
6. If you work on a compiler or scheduler, find where an interference or conflict graph is built and check how ties and spills are decided.