Graph Colouring: Explained with Examples, Notes and FAQs

Graph colouring means assigning a colour to each vertex so that no two adjacent vertices share the same colour. The goal is usually to use as few colours as possible. The smallest number of colours that works is called the graph's chromatic number. The classic example is a map: colour countries so neighbours always differ.

Colouring matters far beyond maps. Exam timetables, radio frequency assignment, register allocation in compilers and Sudoku are all colouring problems: each asks for the fewest "colours" (time slots, frequencies, registers) such that conflicting items never share one.

Key Concepts

• Proper colouring: adjacent vertices always get different colours; non-adjacent vertices may share.
• Chromatic number χ(G): the minimum number of colours needed for a proper colouring.
• Four colour theorem: every planar map can be coloured with at most 4 colours.
• Greedy colouring: colour vertices one by one, each time using the smallest colour not used by an already-coloured neighbour.
• Clique: vertices all pairwise adjacent; a k-clique forces χ(G) ≥ k.

How It Works

Start with any vertex and give it colour 1. Move to the next vertex: give it the lowest colour none of its already-coloured neighbours uses. Continue through all vertices — this greedy method always finishes with at most (maximum degree + 1) colours. To find the true chromatic number, prove fewer colours cannot work: a triangle needs 3, an odd cycle needs 3, a k-clique needs k. Between the greedy upper bound and the clique lower bound sits the real answer. For bipartite graphs it is exactly 2; for odd cycles exactly 3.

Worked Example

Colour a map-graph of four regions: A adjacent to B, C, D; B adjacent to A, C; C adjacent to A, B, D; D adjacent to A, C. Greedy order A, B, C, D: A gets colour 1; B is adjacent to A, so B gets colour 2; C is adjacent to A (1) and B (2), so C gets colour 3; D is adjacent to A (1) and C (3), so D can reuse colour 2. Result: 3 colours. Can 2 work? The triangle A–B–C has all three pairwise adjacent, so it needs 3 distinct colours — a 3-clique forces χ ≥ 3. The chromatic number is exactly 3, and the greedy colouring is optimal here.

Common Misconceptions

• Four colours are not always needed. The four colour theorem says 4 always suffice for planar maps — many maps need only 2 or 3. It is an upper bound, not a requirement.
• Greedy colouring is not always optimal. Colouring vertices in a bad order can waste colours. Finding the best order is itself hard — colouring is NP-complete in general.
• Non-adjacent vertices sharing a colour is allowed — that is the point. Beginners sometimes colour every vertex differently; the skill is reusing colours on vertices that do not touch.

Real-World Applications

• Exam scheduling: courses are vertices, edges join courses sharing students, colours are time slots — adjacent courses never clash.
• Radio frequencies: transmitters are vertices, edges join ones whose signals interfere, colours are frequency bands.
• Compilers: variables alive at the same time are joined by edges; colours are CPU registers.
• Sudoku: each cell is a vertex joined to cells in its row, column and box; a solution is a 9-colouring.

Graph colouring assigns colours so neighbours always differ, and the chromatic number is the fewest colours that can do the job — the mathematics of sharing limited resources among conflicting demands.