Theorem 4.3.1. Thomassen’s 5-Colour Theorem.
For every planar graph \(G\text{,}\)
\begin{equation*}
\chi_\ell(G)\leq 5.
\end{equation*}
Section 4.3 List Colouring
Usually, in graph colouring, one wants to colour the vertices or edges of a graph from a universal palette of \(k\) colours where \(k\) is as small as possible. An interesting variation of this problem is arises when every vertex has its own list of available colours. Say that a list assignment for a graph \(G\) is a function \(L\) which maps each vertex of \(G\) to a set \(L(v)\) of colours. An \(L\)-colouring of \(G\) is a proper colouring \(f\) of \(G\) with the property that \(f(v)\in L(v)\) for all \(v\in V(G)\text{.}\) Given this, we can define the list chromatic number \(\chi_\ell(G)\) of \(G\) to be the minimum \(k\) such that \(G\) has an \(L\)-colouring for every list assignment \(L\) in which \(|L(v)|\geq k\) for all \(v\in V(G)\text{.}\) Of course, by setting all of the lists to be the same, we see that
\begin{equation*}
\chi_\ell(G)\geq\chi(G)
\end{equation*}
for every graph \(G\text{.}\) However, generally speaking, there is no upper bound on the list chromatic number in terms of the chromatic number. In fact, there even exist bipartite graphs (i.e. graphs of chromatic number 2) with arbitrarily large list chromatic number; see Exercise 20. Given that graph colouring problems are NP-hard and list colouring is is seemingly more complicated, it is perhaps not surprising to learn that computing the list chromatic number is NP-hard. In spite of this, many magnificent theorems on list colourings of graphs have been proven over the years, and in this section we will sample some of them.
As we mentioned in Section 4.1, every planar graph has chromatic number at most four. As it turns out, the list chromatic number is not bounded above by four, and the examples that are used to prove this are rather complicated. However, as it turns out, lists of size five do suffice.
Proof.
First, we observe that it suffices to prove the theorem for “near triangulations”, meaning planar graphs in which all faces are triangles except for possibly the outer (infinite) face. So, we prove that all such graphs have list chromatic number at most five. In fact, what we will prove is a stronger (and fairly peculiar seeming) statement. What we will show is that if \(G\) is a near-triangulation and \(L\) is a list assignment for \(G\) such that
- there is an edge \(x_1x_2\) on the boundary of the outer face and such that the lists of \(x_1\) and \(x_2\) have at least one colour each where, if each list has only one colour, then these colours are distinct,
- every vertex on the boundary of the outer face, except for \(x_1\) and \(x_2\text{,}\) has a list of at least three colours and
- every vertex that is not on the boundary of the outer face has a list of at least five colours,
then \(G\) has an \(L\)-colouring. We prove this by induction, where the base cases are easy. Also, by induction, we can assume that the graph is connected.
Suppose that \(G\) has a cut vertex, say \(y\text{.}\) Then at most one of the components of \(G\setminus\{y\}\) intersects \(\{x_1,x_2\}\text{.}\) By induction, the graph induced by the union of this component and \(\{y\}\) can be coloured from the list assignment. After this, for all other components, we colour the graph induced by the union of this component and \(\{y\}\) from the list assignment where \(y\) only has one choice (the colour that it received when colouring the first component) and all other vertices from their original lists. This can be done by induction. Now we glue all of these colourings together to get a colouring of the original graph.
Next, suppose that there is a edge between two non-consecutive vertices on the outer face (which we call a chord). Split the graph into two halves along this chord. One of these halves must contain at most one of \(x_1\) or \(x_2\text{;}\) call this the second half and call the other half the first half. Colour the first half by induction. Then, after doing so, on the second half, we fix the colours of the two vertices of the chord to be equal to their colours in the colouring of the first half and use induction again. Now we glue these two colourings together to get a colouring of the original graph.
Okay, so there is no chord. Let \(v\) be a neighbour of \(x_1\) on the boundary of the outer face that differs from \(x_2\) and let \(c_1\) and \(c_2\) be two colours in \(L(v)\) that are notin \(L(x_1)\text{.}\) Now, delete \(v\) from the graph and remove colours \(c_1,c_2\) from the lists of all neighbours of \(v\) that are on the interior of the graph (i.e. not the neighbours of \(v\) on the boundary). Since there was no chord in \(G\text{,}\) we get that the lists of the vertices on the outer boundary of the new graph now have lists of cardinality at least three, except for \(x_1,x_2\text{.}\) So, we can colour it by induction. Now, just give \(v\) one of the colours \(c_1,c_2\) that is not used on its neighbour other neighbour (other than \(x_1\)) on the outer boundary.
We can also consider list colourings of edges where each edge is assigned to a list and the task is to properly colour the edges using the colours of the lists. The list edge chromatic number of \(G\) is denoted by \(\chi_\ell'(G)\text{.}\) The next theorem is a powerful strengthening of Theorem 4.2.2.
Theorem 4.3.2. Galvin’s Theorem.
For every bipartite graph \(G\text{,}\)
\begin{equation*}
\chi_\ell'(G)=\Delta(G).
\end{equation*}
In order to prove Theorem 4.3.2, we will need one simple tool. Define a kernel in a digraph \(D\) to be a stable set \(K\) (i.e. a set containing no arcs) such that every vertex \(u\in V(D)\setminus K\) has an out-neighbour in \(K\text{.}\) Not all digraphs have kernels; for example, take a directed odd cycle. A digraph is said to be kernel perfect if every induced subdigraph of it contains a kernel. The next lemma connects kernels in digraphs to list colouring.
Lemma 4.3.3.
Let \(G\) be a graph and suppose that \(D\) is a kernel perfect orientation of \(G\text{.}\) If \(L\) is a list assignment for \(G\) such that \(|L(v)|\geq d^+_D(v)+1\) for all \(v\in V(G)\text{,}\) then there exists an \(L\)-colouring of \(G\text{.}\)Proof.
We proceed by induction on the number of vertices where the base case is trivial. Let \(c\) be any colour in \(\bigcup_{v\in V(G)}L(v)\) and define \(A:=\{v\in V(G): c\in L(v)\}\text{.}\) Since \(D\) is kernel perfect, there exists a kernel \(K\) in \(D[A]\text{.}\) Colour all vertices of \(K\) with \(c\text{,}\) delete them from the graph and delete \(c\) from the lists of all remaining vertices. Since \(K\) is a kernel, it is a stable set, and so it is possible to colour these vertices with the same colour. Moreover, since every vertex of \(A\setminus K\) has at least one outneighbour in \(K\text{,}\) deleting the vertices of \(K\) reduces the out-degrees and the sizes of the lists of the vertices of \(A\) by exactly one. Also, the lists of vertices in \(V(G)\setminus A\) do not change. Thus, the remaining graph can be coloured from its list assignment by induction.
We are now ready to prove the theorem.
Proof of Theorem 4.3.2.
Let \(k=\Delta(G)\text{.}\) By Lemma 4.2.1, we can assume that \(G\) is \(k\)-regular. Let \(H\) be the line graph of \(G\text{.}\) By Lemma 4.3.3, it suffices to show that \(H\) has a kernel perfect orientation in which every vertex has out-degree at most \(k-1\text{.}\) For this, we start by taking any proper \(k\)-edge colouring \(f\) of \(G\text{,}\) which exists by Kőnig’s Edge Colouring Theorem (Theorem 4.2.2). Now, for two edges of \(G\) that share a left endpoint, we orient the corresponding edge of \(H\) toward the edge of \(G\) that has a larger colour under \(f\text{.}\) Similarly, if they share a right endpoint, then we orient toward the edge of smaller colour under \(f\text{.}\) Let \(D\) be the resulting digraph. In this orientation, it is not hard to see that every vertex of \(H\) has out-degree exactly \(k-1\text{.}\)
Now, we claim that every induced subdigraph of \(D\) has a kernel. Let \(S\) be any set of vertices in \(D\text{,}\) which corresponds to a set of edges of \(G\text{.}\) Let \(G'\) be the subgraph of \(G\) consisting of the edges in \(S\) and their endpoints. For each vertex \(v\) on the left side of \(G'\text{,}\) we order the neighbours of \(v\) in \(G'\) in such a way that the vertices that are adjacent to \(v\) via edges of larger colour under \(f\) are ranked higher. Similarly, for vertices on the right side, the neighbours along edges of lower colour under \(f\) get a higher ranking. By the Stable Marriage Theorem (in the form of Corollary 3.4.3), there exists a stable matching \(M\) in \(G'\) with respect to these rankings. Clearly, \(M\) corresponds to a stable set in \(D\) (because it is a matching in \(G\)). Also, it is a kernel for \(S\) because, if \(uv\) is an edge of \(G'\) that is not in the matching, then either \(u\) is matched in \(M\) to a vertex that it prefers over \(v\) or \(v\) is matched in \(M\) to a vertex that it prefers over \(v\text{.}\) Either way, the vertex \(uv\) has an out-neighbour (with respect to the digraph \(D\)) in \(M\text{.}\) This completes the proof.
Theorem 4.3.2 together with Theorem 4.2.2 tells us that any bipartite graph \(G\) satisfies \(\chi_\ell'(G) = \chi(G)\text{.}\) A famous unsolved conjecture, known as the List Colouring Conjecture, states that the same is true for every graph.
We mentioned before that there is no upper bound on the list chromatic number in terms of the chromatic number; i.e. the two parameters are “decoupled” from one another. As it turns out, the list chromatic number is more closely linked with the degeneracy of a graph \(G\) which is the maximum of \(\delta(H)\) over all subgraphs \(H\) of \(G\text{,}\) as implied by the following theorem (that we will not prove).
Theorem 4.3.4. Alon.
If \(G\) is a graph of degeneracy \(d\text{,}\) then
\begin{equation*}
\left(\frac{1}{2}-o(1)\right)\log_2(d)\leq \chi_\ell(G)\leq d+1
\end{equation*}
where the \(o(1)\) term tends to zero as \(d\) tends to infinity.Here is a YouTube video related to this section:
