## 5-list-colouring of planar graphs

A $\mathcal{C}-$list-colouring of a graph $\Gamma=(V,E)$ with a colour list $\mathcal{C}=\{C(v_1),\dots,C(v_n)\},$ for $V=\{v_1,\dots,v_n\},$ is a proper colouring of $V$ by elements of $\cup_j C(v_j)$ so that the adjacent vertices $u,v$ are coloured in different colours and the colour for $v\in V$ is in $C(v).$ In particular, when all the $C(v)'$s are equal to each other we have a classic graph colouring.

$\Gamma$ is called $k$-choosable, or $k-$list-colourable if it is $\mathcal{C}-$list-colourable for any $\mathcal{C}$ satisfying $|C(v)|\geq k$ for all $v\in V.$ The minimal $k$ for which is $\Gamma$ is $k-$choosable is called the list chromatic number of $\Gamma$ and denoted by $\chi_\ell(\Gamma).$ Certainly, $\chi(\Gamma)\leq \chi_\ell(\Gamma).$
It is not hard to construct examples when $\chi(\Gamma)< \chi_\ell(\Gamma),$ e.g. take $\Gamma=K_{2,4}$ and consider $\mathcal{C}=\{\{1,2\},\{3,4\},\{1,3\},\{1,4\},\{2,3\},\{2,4\}\},$ where vertices $v_1,v_2$ in the size two part of $\Gamma$ get colour sets $C(v_1)=\{1,2\}, C(v_2)=\{3,4\}$.

Using the fact that each planar graph has a vertex of degree at most 5, as can be easily established using the Euler formula, one can prove that each planar graph is 6-choosable (employ induction by removing a minimal degree vertex).

It is less easy to show that

any planar graph $\Gamma$ is 5-choosable.

This was established in 1994 by Thomassen.
In fact $\chi_\ell(\Gamma)=5$ cannot be improved — there are examples of planar $\Gamma$ for which $\chi_\ell(\Gamma)=5.$ The smallest known (in 2003) example has 63 vertices.

The classical analogy of this, the Heawood theorem that says that each planar graph is 5-colourable, is known since 1890, and the 4-colourability is a recent and quite difficult result by Appel and Haken.

To show the 5-choosability, one first observes that it suffices to prove it for the planar graphs for which every face, except possibly the exterior face of the plane embedding, is a triangle. We call such graphs almost triangulated. Then, one proceeds by induction on $|V|.$ Assume that we know that for any almost triangulated planar $\Gamma$ with $|V\Gamma|\leq n,$ exterior face $B,$ and $\mathcal{C}$ such that $|C(v)|\geq 3$ for all $v \in B,$ resp. $|C(v)|\geq 5$ for all $v\in V\setminus B,$ we can extend a proper $\mathcal{C}$-list-colouring of an edge on $B$ to a full proper $\mathcal{C}$-list-colouring (as is obviously true provided $|V|\leq 3,$ giving us a basis of induction).

Let us now show this for $\Gamma$ with $|V\Gamma|=n+1.$ Let $(x,y)$ be an edge of $B$ that we colour using $\alpha\in C(x)$ and $\beta\in C(y)\setminus\{\alpha\}.$
If $B$ has a chord, i.e. there is an edge $(u,v)$ that joins two non-adjacent vertices of the cycle induced on $B$ (and so $(u,v)$ is not cutting through the fact bounded by the cycle on $B$), we spilt $\Gamma$ into two planar parts $\Gamma_1$ and $\Gamma_2,$ so that $\Gamma_1$ and $\Gamma_2$ have $(u,v)$ in common. W.l.o.g. $(x,y)\in E\Gamma_1;$ by induction, we can extend this colouring to a $\mathcal{C}-$list-colouring $\mathcal{A}_1$ of $\Gamma_1.$ This colouring will fix a proper $\mathcal{C}-$list-colouring of the edge $(u,v),$ that is on the exterior face of $\Gamma_2.$ Again, by induction, we can extend this colouring of $(u,v)$ to a $\mathcal{C}-$list-colouring $\mathcal{A}_2$ of $\Gamma_2.$ Combining $\mathcal{A}_1$ and $\mathcal{A}_2,$ we obtain a $\mathcal{C}-$list-colouring of $\Gamma,$ as required.

It remains to consider the case when $B$ does not have a chord.
Then let $z\in B\setminus\{x,y\}$ be the vertex adjacent to $x.$ Take any two colours $\delta,\mu$ in $C(z)\setminus\{\alpha\}$ (this is possible as $|C(z)|\geq 3$) and remove $\delta,\mu$ from $C(t)$ for all $t\in\Gamma(z)\setminus B.$ Then remove $z$ and all the edges on it from $\Gamma.$ We obtain a planar graph $\Gamma'$ with one vertex less, and with the valid exterior face conditions. By induction, we can extend the colouring of $(x,y)$ to a $\mathcal{C}-$list-colouring of $\Gamma'.$ It remains to see that $z$ can be properly coloured, too. Indeed, we can colour it with either $\delta$ or $\mu,$ depending on the colour of the neighbour of $z$ on $B$ distinct from $x.$ Q.E.D.

### 3 Responses to “5-list-colouring of planar graphs”

1. fs Says:

8) Nice to see a new post here. Yeah, direct induction does work when you just omit non-chordedness from the assumptions for the induction hypothesis.

• Dima Says:

Direct induction without non-chordedness does not work, as you need to prove the claim for an arbitrary boundary edge xy, for which a suitable z (without a chord, that is) need not be there.

• fs Says:

No, I meant that this (what you posted here) works – IIRC in the lecture on the board you had made it a bit more complicated by restricting the induction to only work on graphs that have chords, and then doing a separate induction on cycles (the only remaining class of graphs).