Graph Colouring

Colouring is, alongside planarity, one of the classical topics in graph theory. One of its most celebrated results is the four colour theorem that states that planar graphs can be coloured with just four colours. In this chapter, we first discuss upper bounds on the chromatic number of a graph in terms of the degrees of the vertices, those arising from the greedy colouring algorithm, the Szekeres–Wilf bound and Brooks’ theorem. The weaker theorem of Heawood on planar graphs and the characterisation of planar graphs of low chromatic numbers illustrate the framework of the colouring problem for planar graphs. The better bound given by Vizing’s theorem on the related edge-chromatic number is also discussed, and the equivalence of the four colour theorem with edge-colourings is considered following on from that. The chapter concludes with the list colouring problem, a proof by Thomasen of the 5-choosability of planar graphs and Galvin’s theorem on the edge-choosability of bipartite graphs.