19.3.2. Finding a \(\boldsymbol{k}\)-Colouring

Now that we have two algorithms that decide whether a graph \(G\) has a proper \(k\)-colouring, how do we find such a colouring? Here, we discuss a very simple method: If the decision algorithm answers that \(G\) has no proper \(k\)-colouring, then there is nothing to do. So we assume from here on that \(G\) has a proper \(k\)-colouring. Our strategy is to find a maximal supergraph \(\Delta \supseteq G\) such that \(\Delta\) also has a proper \(k\)-colouring. To construct \(\Delta\), we inspect all vertex pairs \((u,v)\) such that \((u,v)\) is not an edge in \(G\). For each such pair, we test whether \(G \cup \{(u,v)\}\) has a proper \(k\)-colouring. If so, we add \((u,v)\) to \(G\) and proceed to the next edge. Otherwise, we proceed to the next edge without altering \(G\). The graph obtained after inspecting all such edges \((u,v)\) absent from \(G\) is \(\Delta\). By construction, \(\Delta\) has a proper \(k\)-colouring. Since \(\Delta \supseteq G\), any proper \(k\)-colouring of \(\Delta\) is a proper \(k\)-colouring of \(G\). To find a proper \(k\)-colouring of \(\Delta\), we consider the complement \(\bar\Delta\) of \(\Delta\), which contains an edge \((u,v)\) if and only if \(\Delta\) does not. Now consider the vertex colouring \(\gamma\) that assigns the same colour to all vertices in the same connected component of \(\bar\Delta\) and different colours to vertices in different connected components of \(\bar\Delta\).

Lemma 19.13: \(\gamma\) is a proper \(k\)-colouring of \(\Delta\).

Proof: First we prove that \(\gamma\) is a \(k\)-colouring. Let \(\bar\Delta_1, \ldots, \bar\Delta_r\) be the connected components of \(\bar\Delta\). Then \(\gamma\) is an \(r\)-colouring. We need to show that \(r \le k\). Let \(\{v_1, \ldots, v_r\}\) be a set of vertices such that \(v_i \in \bar\Delta_i\) for all \(1 \le i \le r\). By definition, \(\bar\Delta[\{v_1, \ldots, v_r\}]\) has no edges, so \(\Delta[\{v_1, \ldots, v_r\}]\) is a clique and any proper colouring of \(\Delta\) needs to use at least \(r\) colours. Since \(\Delta\) has a proper \(k\)-colouring, this implies that \(r \le k\).

To prove that \(\gamma\) is a proper colouring of \(\Delta\), recall that \(\Delta\) has a proper \(k\)-colouring \(\gamma'\). We prove that \(\gamma(u) = \gamma(v)\) implies that \(\gamma'(u) = \gamma'(v)\), for every pair \((u,v)\) of vertices. Thus, \(\gamma(u) = \gamma(v)\) implies that \((u,v) \notin \Delta\), so \(\gamma\) is a proper colouring of \(\Delta\).

We have \(\gamma(u) = \gamma(v)\) if and only if \(u\) and \(v\) belong to the same connected component of \(\bar\Delta\). First consider the case when \((u,v) \in \bar\Delta\). Then \((u,v) \notin \Delta\). Thus, by the definition of \(\Delta\), the graph \(\Delta \cup \{(u,v)\}\) has no proper \(k\)-colouring, that is, \(\gamma'(u) = \gamma'(v)\). If \((u,v) \notin \bar\Delta\) but \(u\) and \(v\) belong to the same connected component of \(\bar\Delta\), then there exists a path \(\langle u = x_0, \ldots, x_t = v \rangle\) from \(u\) to \(v\) in \(\bar\Delta\). By the argument just made for vertices connected by an edge in \(\bar\Delta\), we have \(\gamma'(u) = \gamma'(x_0) = \cdots = \gamma'(x_t) = \gamma'(v)\). ▨

Corollary 19.14: It takes \(O^*(2^n)\) time and space or \(O^*(3^n)\) time and polynomial space to decide whether a graph \(G\) has a proper \(k\)-colouring and, if so, find such a colouring.

Proof: Let \(\mathcal{A}\) be an algorithm to decide whether a graph has a proper \(k\)-colouring. By running this algorithm on \(G\), we decide whether \(G\) has a proper \(k\)-colouring. If the answer is affirmative, it takes at most \(\binom{n}{2}\) additional applications of this algorithm to construct \(\Delta\). Given \(\Delta\), constructing \(\bar\Delta\) and computing and colouring its connected components takes \(O\bigl(n^2\bigr)\) time.

If \(T_\mathcal{A}\) and \(S_\mathcal{A}\) are the running time and space requirements of \(\mathcal{A}\), this algorithm to compute a \(k\)-colouring of \(G\) takes \(T_\mathcal{A} \cdot O\bigl(n^2\bigr)\) time and \(S_\mathcal{A}\) space. The corollary now follows by using Corollary 19.10 or 19.12 to provide the algorithm \(\mathcal{A}\). ▨