Graph Coloring Solver

Pseudocode

Greedy colouring is three lines and always produces a valid colouring. What it does not produce is necessarily a minimal one, and the vertex order decides how close it gets.

GreedyColoring(graph, order):
    color = {}
    for each vertex v in order:
        used = { color[n] : n in neighbors(v), n colored }
        c = smallest positive integer not in used
        color[v] = c
    return color

// Welsh-Powell: order by descending degree
// DSatur: repeatedly pick the uncolored vertex with the
//         most distinctly-colored neighbors (saturation),
//         breaking ties by degree

Greedy never uses more than max degree plus one colours, because when you reach a vertex it has at most that many neighbours and so at most that many forbidden colours. That is a genuine guarantee, but it can be far from the true chromatic number. DSatur is the practical improvement: choosing the most constrained vertex next is exactly the heuristic that avoids painting yourself into a corner.

Worked example, step by step

Colour a five-cycle greedily in alphabetical order, then check the result against the true chromatic number.

Example graph: Undirected cycle A-B, B-C, C-D, D-E and E-A.

1. Colour A. No neighbours are coloured yet, so A takes colour 1.
2. Colour B. B is adjacent to A, which has colour 1, so the smallest available is colour 2.
3. Colour C. C is adjacent to B (colour 2) and to the still uncoloured D. Colour 1 is free, so C takes 1.
4. Colour D. D is adjacent to C (colour 1) and uncoloured E. Colour 2 is free, so D takes 2.
5. Colour E forces a third. E is adjacent to D (colour 2) and to A (colour 1). Both existing colours are taken, so E needs colour 3.

The colouring is A 1, B 2, C 1, D 2, E 3, using three colours, and brute force confirms the chromatic number of a five-cycle really is 3. Greedy happened to be optimal here. The reason three are needed at all is that the cycle has odd length: colours must alternate around a cycle, and an odd cycle brings you back to the start needing a colour different from the one already there. Every even cycle needs only 2.

Complexity, and where it comes from

Time: O(V + E) greedy, NP-hard exactly · Space: O(V)

Greedy colouring examines each vertex once and inspects each edge twice, once from each endpoint, so it is O(V + E) with O(V) space for the colour array. That cost buys a valid colouring using at most max degree plus one colours, never a guaranteed minimum. Computing the actual chromatic number is NP-hard, and even approximating it within a factor of V to the power 1 minus epsilon is NP-hard, which is unusually strong: for most problems some decent approximation exists, and for colouring essentially none does. Deciding 2-colourability is the exception and is easy, since it is exactly the bipartiteness test at O(V + E). Deciding 3-colourability is already NP-complete.

When to use Graph Coloring, and when not to

Pick by how many colours you expect to need and whether you require the true minimum.

Common pitfalls

• Assuming greedy gives the chromatic number. It gives a valid colouring, not a minimal one, and the gap can be large. On the crown graph with parts {a1,a2,a3} and {b1,b2,b3} where ai joins bj whenever i differs from j, the interleaved order a1,b1,a2,b2,a3,b3 makes greedy use 3 colours even though the graph is bipartite and 2 suffice. Ordering the same graph as a1,a2,a3,b1,b2,b3 gets 2.
• Ignoring how much the vertex order matters. Some order always achieves the true chromatic number, and finding it is as hard as the colouring problem itself. This is why DSatur chooses dynamically as it goes rather than fixing an order upfront.
• Confusing chromatic number with clique number. A clique of size k forces at least k colours, so the clique number is a lower bound, but the two can differ. Odd cycles of length 5 or more need 3 colours while containing no triangle at all.
• Expecting a good approximation to exist. Unlike many NP-hard problems, graph colouring has no known constant-factor approximation and strong hardness results say none is likely. Heuristics can do well in practice but carry no worst-case guarantee.
• Forgetting self-loops make it impossible. A vertex adjacent to itself can never be coloured differently from itself, so a graph with a self-loop has no proper colouring at all. Reject those before starting.

Frequently asked questions

What is graph colouring?

Graph colouring assigns a colour to each vertex so that no two adjacent vertices share one. The smallest number of colours that works is the chromatic number of the graph. It models any problem where conflicting items must be separated, such as scheduling exams so no student sits two at once.

What is the chromatic number of a graph?

The minimum number of colours needed for a proper colouring. A bipartite graph has chromatic number 2 or less, an odd cycle has 3, and a complete graph on n vertices has n. Computing it in general is NP-hard, though a clique of size k gives an easy lower bound of k.

Does the greedy algorithm always use the fewest colours?

No. It always produces a valid colouring using at most max degree plus one colours, but that can exceed the chromatic number. On the crown graph, a bipartite graph needing only 2 colours, an unlucky vertex order makes greedy use 3. Some order always achieves the optimum, but finding it is as hard as the original problem.

What is the difference between greedy colouring and DSatur?

Greedy fixes a vertex order in advance and colours in that order. DSatur chooses the next vertex dynamically, always taking the one with the most distinctly coloured neighbours and breaking ties by degree. That focus on the most constrained vertex makes DSatur optimal on bipartite graphs and much better in general, at O(V squared) rather than O(V + E).

What is graph colouring used for?

Register allocation in compilers, where registers are colours and interfering variables are adjacent. Also exam and shift scheduling, radio frequency assignment to avoid interference between nearby transmitters, Sudoku solving, and separating conflicting tasks in any resource allocation problem.