1
It models conflict
Exam scheduling, register allocation, frequency assignment. An edge means "cannot share", and a colour is a resource.
Lesson · Graphs and Trees · Colouring and planarity
Graph Colouring
The chromatic number is the fewest colours needed. Two colours is a linear test, three is NP-complete, and the four-colour theorem says planar graphs never need more than four.
proper colouring: adjacent vertices get different colours
χ(G) = chromatic number = fewest colours needed
χ = 2 ⟺ bipartite — linear-time test
deciding χ ≤ 3 is NP-complete; greedy uses at most Δ + 1
Easy at two, hard at three
Core ideas
What this lesson establishes
Colouring models conflict: adjacent things cannot share a resource, and the chromatic number is how many resources are needed.
2
Greedy is fast and not optimal
It never uses more than Δ + 1 colours, and the visiting order can cost it colours it did not need.
3
Two is easy, three is hard
χ ≤ 2 is one search; χ ≤ 3 is NP-complete. The boundary between easy and hard is exactly there.
The material
Colouring
The definition, bounds, the greedy algorithm, and the four-colour theorem.
Definition · Proper colouring, chromatic number
A proper colouring assigns a colour to each vertex so that adjacent vertices differ. The chromatic number χ(G) is the smallest number of colours admitting one.
χ(Kₙ) = n every pair adjacent
χ(Cₙ) = 2 if n even, 3 if n odd
χ(tree) = 2 for any tree with an edge
χ(bipartite) = 2 by definition, for a graph with an edge
Theorem · Two colours
χ(G) ≤ 2 if and only if G is bipartite, if and only if G has no odd cycle. Testable in Θ(n + |E|) by “Bipartite Graphs”.
Theorem · Greedy bound
Colouring the vertices in any order, giving each the smallest colour unused by its already-coloured neighbours, uses at most Δ + 1 colours, where Δ is the maximum degree.
When a vertex is coloured, it has at most Δ neighbours, so at most Δ colours are forbidden. Among Δ + 1 colours one is always available.
□
Brooks's theorem sharpens this: χ(G) ≤ Δ unless G is a complete graph or an odd cycle, which are the two families needing Δ + 1.
Greedy is not optimal, and the order is what costs it. On a bipartite graph a bad order can use many colours where two suffice, which is why the algorithm is a bound rather than a solution.
Theorem · Colouring is hard
Deciding whether χ(G) ≤ 3 is NP-complete, and computing χ(G) exactly is NP-hard. Even approximating it well is hard.
The jump from 2 to 3 is the sharpest example on this path of a problem changing character with a parameter. Nothing in the statements suggests it, and “P, NP and NP-Completeness” in Algorithms and Complexity explains what NP-complete means.
The four-colour theorem
Theorem · Four colours suffice
Every planar graph has χ(G) ≤ 4.
Conjectured in 1852 and proved by Appel and Haken in 1976, with a proof that reduced the problem to 1936 configurations and checked them by computer. It was the first major theorem whose proof could not be verified by a human reading it, and the resulting argument about what counts as a proof has not entirely settled.
The five-colour theorem, by contrast, has a short human proof by induction using Euler's formula from “Planar Graphs and Euler's Formula”. Four is genuinely harder than five.
Applications
- Exam scheduling. Vertices are exams, edges join exams sharing a student, colours are time slots. χ is the fewest slots needed.
- Register allocation. Vertices are variables, edges join variables live at the same time, colours are CPU registers. Compilers do this constantly — and use heuristics, since the problem is NP-hard.
- Frequency assignment. Vertices are transmitters, edges join those that would interfere, colours are frequencies.
- Sudoku. A 9-colouring problem on a graph with 81 vertices and an edge for every row, column and box constraint.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Colouring a graph
Bound first, then colour.
1
Look for a large complete subgraph
A Kₖ inside G forces χ ≥ k. This is the standard lower bound and it is often tight.
2
Check bipartiteness
If the graph is bipartite, χ = 2 and you are finished. One search.
3
Run greedy for an upper bound
At most Δ + 1 colours. Trying several vertex orders often reduces it.
4
Compare the bounds
If the clique lower bound meets the greedy upper bound, that value is χ. Otherwise exact computation is expensive.
Colouring
Score 0 / 0Choose the answer you can justify.
Scheduling exams
Five exams; edges join exams with a student in common.
edges: A–B, A–C, B–C, B–D, C–D, D–E
A, B, C are mutually adjacent — a triangle — so χ ≥ 3.
Greedy in order A, B, C, D, E:
A colour 1
B adjacent to A colour 2
C adjacent to A and B colour 3
D adjacent to B and C colour 1
E adjacent to D colour 2
3 colours used, and χ ≥ 3, so χ = 3.
Three time slots: {A, D} {B, E} {C}
The triangle gave the lower bound and greedy gave the upper, and they met — which is the only cheap way to be certain. Without a matching lower bound, greedy's answer is an upper bound and nothing more.
Common mistakes
1
Treating greedy's answer as χIt is an upper bound. A different vertex order may use fewer colours, and χ may be lower than any order achieves quickly.
2
Assuming a planar graph needs four coloursFour suffice; many planar graphs need two or three. The theorem is an upper bound.
3
Forgetting the clique lower boundA Kₖ inside the graph forces χ ≥ k, and it is usually the easiest lower bound to find.
Check your understanding
✓
Finish when you can bound χ from both sides.
For a graph of your own, find the largest complete subgraph you can and run greedy. If the two numbers meet you have χ exactly; if not, you have located the difficulty.
Note: Register allocation in compilers is graph colouring on a graph with thousands of vertices, solved by heuristics because the exact problem is NP-hard. It is one of the most economically significant applications of anything on this path.