Discrete Math › Section C · Graph theory › Topic C.6

Coloring graphs

How few exam slots can a college use so that no student has two exams at once? How few colours does a map need? Both are graph colouring problems, and they lead from quick counting arguments to one of the most famous computer-assisted proofs in mathematics.

Conflicts as edges

A college must schedule six exams. Two exams conflict if some student takes both, so they cannot share a time slot. Draw a vertex for each exam and an edge for each conflict. Now give each vertex a colour standing for its time slot. The schedule works exactly when the two ends of every edge get different colours, and the fewest slots needed is the fewest colours that work. The same model fits radio stations that must use different frequencies when close together, and registers in a compiler shared by variables that are never needed at the same time.

Proper colourings and the chromatic number

A proper colouring of a graph assigns a colour to each vertex so that adjacent vertices always get different colours. A graph is \(k\)-colourable if it has a proper colouring with at most \(k\) colours. The chromatic number \(\chi(G)\) is the smallest such \(k\). Proving that \(\chi(G) = k\) always takes two steps: show a proper colouring with \(k\) colours, which proves \(\chi(G) \le k\), and give a reason why \(k - 1\) colours cannot work, which proves \(\chi(G) \ge k\).

Graphs you can colour at a glance

In \(K_n\) every pair is adjacent, so all \(n\) vertices need different colours: \(\chi(K_n) = n\). A graph with at least one edge needs at least 2 colours, and it needs exactly 2 precisely when it is bipartite: the two sides are the two colours. A graph is bipartite if and only if it has no cycle of odd length. So every tree with at least two vertices has \(\chi = 2\), an even cycle has \(\chi = 2\), and an odd cycle has \(\chi = 3\). Going round an odd cycle, two colours would have to alternate an odd number of times and clash at the end.

Lower bounds: cliques

A clique is a set of vertices that are all adjacent to one another, a copy of \(K_m\) inside the graph. The clique number \(\omega(G)\) is the size of the largest clique. Every vertex of a clique needs its own colour, so

\chi(G) \ge \omega(G)

This gives a quick lower bound, but it can fall short. The 5-cycle has no triangle, so its clique number is 2, yet as an odd cycle it needs 3 colours. Graphs need many colours for reasons other than large cliques.

Upper bounds: greedy colouring and Brooks' theorem

The greedy algorithm takes the vertices in some order and gives each the lowest-numbered colour not already used by its coloured neighbours. A vertex of degree \(d\) has at most \(d\) neighbours, so it always finds a free colour among the first \(d + 1\). If \(\Delta(G)\) is the largest degree, then \(\chi(G) \le \Delta(G) + 1\). Brooks' theorem improves this by one: a connected graph that is neither a complete graph nor an odd cycle has \(\chi(G) \le \Delta(G)\). The two exceptions really do need \(\Delta + 1\), as \(K_n\) and the odd cycles show.

Worked example: scheduling six exams

Exams A to F conflict in these pairs: AB, AC, BC, BD, CE, DE, DF, EF. 1. Lower bound: A, B and C are pairwise in conflict, a triangle, so at least 3 slots are needed. 2. Greedy colouring in the order A to F: A gets slot 1, B slot 2 and C slot 3. D's neighbours are B, E and F, and only B is coloured, with 2, so D gets 1. E's coloured neighbours C and D hold 3 and 1, so E gets 2. F's neighbours D and E hold 1 and 2, so F gets 3. 3. Slots: {A, D}, {B, E}, {C, F}, and no pair inside a slot conflicts. So \(\chi = 3\): three slots, and no fewer.

Worked example: when greedy and cliques mislead

1. Greedy depends on order. On the path a-b-c-d, colour in the order a, d, b, c. Then a gets 1 and d gets 1, b, next to a, gets 2, and c, next to b and d, gets 3. Three colours, though the path is bipartite and 2 suffice. 2. Cliques can understate the answer. Take a hub joined to every vertex of a 5-cycle. The largest clique is a triangle, so \(\omega = 3\). But the 5-cycle alone needs 3 colours, and the hub, adjacent to all five, needs a fourth. So \(\chi = 4 > \omega\). With a 6-cycle round the hub instead, 3 colours suffice.

Maps and the four colour theorem

To colour a map so that neighbouring countries differ, make each country a vertex and join two countries that share a stretch of border, not just a single point. For a map whose countries are connected regions, this graph is planar. The four colour theorem states that every planar graph has \(\chi(G) \le 4\). It was proved by Kenneth Appel and Wolfgang Haken in 1976 with a computer checking a very large number of cases, and it sparked debate about whether such a proof is fully convincing. A weaker result is easy: the bound \(e \le 3v - 6\) forces every simple planar graph to have a vertex of degree at most 5, which leads to a short proof that 6 colours always suffice.

Colouring edges

Sometimes the edges need colours. In a proper edge colouring, edges that share a vertex get different colours, and the fewest colours needed is the chromatic index \(\chi'(G)\). The edges at a vertex of degree \(\Delta\) all differ, so \(\chi'(G) \ge \Delta(G)\). Vizing's theorem says a simple graph needs either \(\Delta\) or \(\Delta + 1\) colours, and bipartite graphs always need exactly \(\Delta\). For a round-robin tournament, edges are games and colours are rounds: the 6 games among 4 teams fit into 3 rounds, but 3 teams need 3 rounds for their 3 games.

Common mistakes to avoid

First, stopping after finding a colouring: a colouring with \(k\) colours shows only that \(\chi \le k\), so you also need a reason fewer colours fail. Second, assuming \(\chi\) equals the clique number; the hub-and-5-cycle graph has \(\chi = 4\) with no \(K_4\). Third, trusting one greedy run as optimal. Fourth, treating regions that meet at a single point as neighbours in a map. Fifth, thinking the four colour theorem covers every graph: \(K_5\) needs 5 colours, but it is not planar.

Key takeaways

A proper colouring gives adjacent vertices different colours, and \(\chi(G)\) is the fewest colours needed; it models scheduling and frequency assignment. Bipartite graphs, including trees and even cycles, need 2 colours, odd cycles need 3 and \(K_n\) needs \(n\). Cliques give lower bounds, \(\chi \ge \omega\); greedy colouring gives \(\chi \le \Delta + 1\), and Brooks' theorem gives \(\chi \le \Delta\) apart from complete graphs and odd cycles. Every planar graph is 4-colourable, and a simple graph's edges need \(\Delta\) or \(\Delta + 1\) colours.

Flashcards

Flashcard

Proper colouring

Adjacent vertices always get different colours

Colours can stand for time slots.

Test your understanding

Question 1 of 5

What is the chromatic number of the cycle C₉?

Question 2 of 5

Four exams each share at least one student with each of the other three. What is the smallest number of time slots these four exams need?

Question 3 of 5

A hub vertex is joined to all five vertices of a 5-cycle. What is the chromatic number of this graph?

Question 4 of 5

A connected graph has largest degree 4 and is neither a complete graph nor an odd cycle. What does Brooks' theorem guarantee?

Question 5 of 5

Which statement is the four colour theorem?

← Previous topicNext topic →