Lesson 5

Theorem. Any planar graph \(G\) is list 5-colorable.

Proof. Consider some embedding of the graph and assume that all internal faces are triangles: if there is a face that is not a triangle, we can add a chord to it — this does not decrease the list chromatic number.

The statement of the theorem follows from the following stronger claim, which we will prove by induction (and thus use a stronger induction hypothesis!).◼

Lemma. Let \(G(V,E)\) be a planar graph in which all internal faces are triangles, and let \(C\) be the cycle bounding the outer face. Suppose also that:

1. two adjacent vertices \(u,v\) of the cycle \(C\) are already colored in different colors \(c(u)\) and \(c(v)\);
2. for all other vertices \(w\) of the cycle \(C\) we have \(|L(w)| \ge 3\);
3. for all internal vertices \(w\) we have \(|L(w)| \ge 5\).

Proof. We prove by induction on the number of vertices. If there are only three vertices, the claim is obviously true. Now suppose there are more than three. Consider two cases.

1. There is a chord in \(C\): there are two vertices of the cycle \(a\) and \(c\) that are connected by an edge not belonging to the cycle.

   

   This chord divides the graph into two parts. Color by induction the part containing the vertices \(u,v\). Then the vertices \(a,c\) will be colored somehow, and the second part can also be colored by induction.

2. There is no such chord. Let \(w\) be the neighbor of \(v\), distinct from \(u\), in the cycle \(C\). Now consider the graph \(H=G-w\). All neighbors of \(w\) in \(G\) fall onto the boundary of \(H\) (since the graph is triangulated).

   

   Recall that \(|L(w)| \ge 3\). Take two colors \(i,j \in L(w) - c(v)\) and remove them from the lists of all neighbors of \(w\) that lie inside the cycle \(C\). Thus, the graph \(H\) and its vertex lists satisfy all conditions of the lemma, so it can be properly colored. After that, we can finish by coloring the vertex \(w\) with one of the colors \(i,j\) different from the color of its neighbor.