The exam timetable
A school must schedule seven exams. Two exams can't be at the same time if any student is taking both. Draw each exam as a vertex and join two exams whenever they share a student. This is called a conflict graph.
The conflicts
A timetable with 3 slots
A timetable is just an assignment of a colour (a time slot) to each vertex, with one rule: vertices joined by an edge must get different colours. Using as few colours as possible means fitting the exams into as few slots as possible.
Could we manage with only 2 slots? No: Maths, Physics and Chem are all joined to each other (a triangle). Three mutually clashing exams need three different slots. So 3 is the best possible here.
The chromatic number
Definitions
A proper colouring of a graph gives each vertex a colour so that adjacent vertices always get different colours. Using k colours, it's called a k-colouring.
The chromatic number χ(G) (χ is the Greek letter "chi") is the smallest k for which a k-colouring exists.
To prove that χ(G) = k, you need two things: a colouring with k colours (showing k is enough), and a reason why k − 1 colours can't work (showing k is needed). For the exam graph: the colouring above, plus the triangle.
χ = 4complete graph K4
χ = 2even cycle C6
χ = 3odd cycle C5
χ = 2any tree
χ = 2bipartite K2,3
χ = 4wheel with 5 spokes
Try it. What is the chromatic number of the friendship graph from Unit 1 (Ana–Ben, Ana–Cara, Ben–Cara, Ben–Dev, Cara–Eli, Dev–Eli, Eli–Fay)?
Show answer
3. Ana, Ben and Cara form a triangle, so at least 3 colours are needed. Three are enough: Ana 1, Ben 2, Cara 3, Dev 1, Eli 2, Fay 1. (Check: Dev–Ben is 1–2, Dev–Eli is 1–2, Cara–Eli is 3–2, Eli–Fay is 2–1.)
Two colours: bipartite graphs
A graph can be coloured with 2 colours exactly when its vertices split into two groups with no edges inside a group, which is the definition of bipartite (Unit 1). There's a neat way to recognise these graphs:
Theorem
A graph is bipartite (2-colourable) if and only if it has no cycle of odd length.
One direction is easy: going round a cycle, colours must alternate 1, 2, 1, 2, …, which only returns to the start correctly if the cycle has an even number of vertices. For the other direction, run breadth-first search (Unit 4) and colour each vertex by whether its distance from the start is even or odd. If two vertices of the same colour are joined by an edge, you can follow the BFS tree to build an odd cycle. So 2-colourability can be tested quickly.
That's why trees always need just 2 colours (they have no cycles at all), and why "can this group be split into two teams with no rivals on the same team?" is an easy question.
Lower and upper bounds
For 3 colours and more, things get hard. Deciding whether a graph can be 3-coloured is NP-complete, in the same family as the Hamilton cycle problem of Unit 6. No fast method is known. So in practice we sandwich χ between bounds:
- Lower bound from cliques. A clique is a set of vertices all joined to each other (Unit 1). If the largest clique has k vertices, at least k colours are needed. But the chromatic number can be bigger than the largest clique: C5 has no triangle, yet needs 3 colours.
- Upper bound from degrees. If no vertex has more than Δ neighbours, then Δ + 1 colours are always enough. Colour the vertices one at a time; each vertex's neighbours can use up at most Δ colours, so there's always one left over.
- Brooks' theorem (1941) sharpens this: χ ≤ Δ for every connected graph except complete graphs and odd cycles, which need exactly Δ + 1.
Greedy colouring
The upper-bound argument is also an algorithm. Greedy colouring: put the vertices in some order and give each one the smallest colour number not used by its already-coloured neighbours. It's fast and never uses more than Δ + 1 colours. But the result depends heavily on the order:
A popular improvement is to colour the vertices with the most neighbours first (the Welsh–Powell order), since they're the hardest to fit in later. There's always some order for which greedy finds the optimum, but finding that order is as hard as the original problem.
Try it. Run greedy colouring on the exam graph in the order Maths, Physics, Chem, Bio, History, Art, Music. How many colours does it use?
Show answer
Maths 1. Physics (next to Maths) 2. Chem (next to Maths, Physics) 3. Bio (next to Chem 3, Physics 2) 1. History (next to Bio 1) 2. Art (next to History 2) 1. Music (next to Art 1, Maths 1, History 2) 3. 3 colours, which is optimal. It's the colouring in the figure.
Maps and the four colour theorem
In 1852 Francis Guthrie was colouring a map of the counties of England and noticed he never needed more than four colours, so that neighbouring counties always had different colours. Was that always true, for every possible map?
A map becomes a graph by putting a vertex in each region and joining two vertices when the regions share a border (touching at a single point doesn't count):
The map
Its graph: K4
Graphs that come from maps can always be drawn without crossing edges: they are planar graphs, the subject of Unit 10. So the question becomes: can every planar graph be coloured with 4 colours?
The four colour theorem (Appel and Haken, 1976)
Every planar graph can be properly coloured with at most four colours. So every map can be coloured with four colours so that neighbouring regions differ.
Watch out
The theorem is about maps where every country is one connected piece. Real maps have countries in several pieces (with islands or exclaves), and since all pieces of a country must share its colour, those maps can need more than four colours. Lakes and seas are usually coloured separately, too.
Colouring edges: round robins
Sometimes it's the edges that need colours. Four teams play a round-robin tournament (Unit 1): every pair plays once. Each team can play only one match per round. How many rounds are needed?
Each round is a set of matches with no team playing twice: a matching (Unit 7). Giving each match the colour of its round is an edge colouring: edges that share a vertex must get different colours. A vertex with d edges needs at least d colours around it, so at least Δ colours are needed overall. Vizing's theorem (1964) says that Δ + 1 always suffice, so the answer is always Δ or Δ + 1.
Try it. How many rounds does a round robin need for 6 teams? For 5 teams?
Show answer
6 teams: 5 rounds. Each team plays 5 matches, so at least 5 rounds are needed, and a schedule with 3 matches per round exists. 5 teams: 5 rounds. Each team plays only 4 matches, but with an odd number of teams one team must sit out each round, so each round has at most 2 matches. There are 10 matches, so at least 5 rounds are needed.
Colouring in the real world
- Sudoku. Make each of the 81 squares a vertex, joined to the 20 others in its row, column and box. A solved Sudoku is a proper 9-colouring of this graph (the colours are the digits 1 to 9), and the puzzle asks you to complete a partial colouring.
- Radio and mobile frequencies. Transmitters close enough to interfere must use different frequencies. Colours are frequencies, and fewer colours means less precious radio spectrum.
- Computer memory. When software is compiled, variables that are in use at the same time can't share a fast processor register. Compilers colour this "interference graph" with the registers as colours.
- Traffic lights. Traffic flows at a junction that would cross each other can't have a green light at the same time. Colours are phases of the lights.
- Seating and storage. Guests who don't get on, or chemicals that react together, must be placed at different tables or in different cupboards.
Practice set
Mixed questions covering the whole unit. Try each one before opening the answer.
1. What is the chromatic number of K7? Of the complete bipartite graph K5,8?
Show answer
K7: 7. K5,8: 2, colour each side with its own colour.
2. A graph has a vertex of degree 10 and every other vertex has degree at most 3. Is 4 colours always enough?
Show answer
Yes. Colour the high-degree vertex first, with colour 1, then greedily colour the rest. Every other vertex has at most 3 neighbours, so among 4 colours one is always free. (The Δ + 1 = 11 bound is far too pessimistic here: the order of colouring matters.)
3. Is it possible for a graph with no triangles to need 4 colours?
Show answer
Yes. The Grötzsch graph has 11 vertices, no triangles, and chromatic number 4. In fact there are triangle-free graphs needing any number of colours you like, so cliques can badly underestimate χ.
4. A conflict graph for 8 exams has its largest clique of size 3 and maximum degree 5. What can you say about the number of time slots needed?
Show answer
3 ≤ χ ≤ 6. At least 3 slots (the clique), at most Δ + 1 = 6. By Brooks' theorem, unless the graph is a complete graph or an odd cycle (it isn't: its largest clique is only 3), at most 5.
5. Can a map of 5 regions need 5 colours?
Show answer
No. By the four colour theorem, 4 always suffice. In particular, it's impossible to draw 5 regions that all border each other: that would need the graph K5 to be planar, and Unit 10 shows it isn't.
6. Which of these graphs are 2-colourable: the cube's corners and edges; the triangular prism; a 10-cycle with one diagonal joining opposite vertices?
Show answer
Cube: yes (colour corners by whether they have an even or odd number of "1"s in their coordinates). Prism: no, it contains triangles. 10-cycle plus opposite diagonal: yes. Opposite vertices are 5 steps apart, so the diagonal creates two cycles of length 6, both even. With alternating colours, vertices 5 apart get different colours.
Summary and glossary
- A proper colouring gives neighbours different colours. Colours can stand for time slots, frequencies, registers or rounds.
- The chromatic number χ is the fewest colours possible. Kn needs n; even cycles need 2; odd cycles need 3.
- A graph is 2-colourable exactly when it has no odd cycle, and this is quick to test. 3-colourability is NP-complete.
- Largest clique ≤ χ ≤ Δ + 1. Greedy colouring achieves the upper bound, and its result depends on the order.
- The four colour theorem: every planar graph, and so every map, can be coloured with 4 colours.
- Edge colouring schedules round robins; it needs Δ or Δ + 1 colours.
- Proper colouring
- Colours on vertices so that adjacent vertices differ.
- Chromatic number χ
- The smallest number of colours in a proper colouring.
- Conflict graph
- A graph joining things that can't share a colour (slot, frequency, …).
- Clique
- A set of vertices all joined to each other.
- Greedy colouring
- Colouring vertices in order, each with the smallest colour available.
- Planar graph
- A graph that can be drawn with no crossing edges.
- Four colour theorem
- Every planar graph can be 4-coloured.
- Edge colouring
- Colours on edges so that edges sharing a vertex differ.