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.


Tags: , , , ,

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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: