19.3. Graph Colouring

The second problem we consider in this section is probably one of the most iconic NP-hard problems:

A vertex colouring of a graph \(G\) assigns a colour to every vertex of \(G\). A vertex colouring is proper if there is no edge whose endpoints have the same colour. This is illustrated in Figure 19.1.

Figure 19.1: Coming soon!

A \(\boldsymbol{k}\)-colouring is a vertex colouring of \(G\) using at most \(k\) colours.

Graph Colouring Problem: Given a graph \(G = (V, E)\) and an integer \(k\), decide whether \(G\) has a proper \(k\)-colouring, and find one if one exists.

We proceed in three phases: First, we discuss how to decide, in \(O^*(2^n)\) time, whether there exists a proper \(k\)-colouring of \(G\). This algorithm uses exponential space. We reduce its space requirements to linear at the expense of increasing its running time to \(O^*(3^n)\). Finally, we apply self-reduction again to find an actual \(k\)-colouring, either in \(O^*(2^n)\) time and exponential space or in \(O^*(3^n)\) time and linear space.