A list-colouring of a graph with a colour list for is a proper colouring of by elements of so that the adjacent vertices are coloured in different colours and the colour for is in In particular, when all the s are equal to each other we have a classic graph colouring.

is called -choosable, or list-colourable if it is list-colourable for any satisfying for all The minimal for which is is choosable is called the list chromatic number of and denoted by Certainly,

It is not hard to construct examples when e.g. take and consider where vertices in the size two part of get colour sets .

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 is 5-choosable.

This was established in 1994 by Thomassen.

In fact cannot be improved — there are examples of planar for which 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 Assume that we know that for any almost triangulated planar with exterior face and such that for all resp. for all we can extend a proper -list-colouring of an edge on to a full proper -list-colouring (as is obviously true provided giving us a basis of induction).

Let us now show this for with Let be an edge of that we colour using and

If has a chord, i.e. there is an edge that joins two non-adjacent vertices of the cycle induced on (and so is not cutting through the fact bounded by the cycle on ), we spilt into two planar parts and so that and have in common. W.l.o.g. by induction, we can extend this colouring to a list-colouring of This colouring will fix a proper list-colouring of the edge that is on the exterior face of Again, by induction, we can extend this colouring of to a list-colouring of Combining and we obtain a list-colouring of as required.

It remains to consider the case when does not have a chord.

Then let be the vertex adjacent to Take any two colours in (this is possible as ) and remove from for all Then remove and all the edges on it from We obtain a planar graph with one vertex less, and with the valid exterior face conditions. By induction, we can extend the colouring of to a list-colouring of It remains to see that can be properly coloured, too. Indeed, we can colour it with either or depending on the colour of the neighbour of on distinct from Q.E.D.

Tags: combinatorics, graph theory, MAS324, maths, teaching

8 September, 2009 at 14:23 |

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.

24 November, 2010 at 13:22 |

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.

24 November, 2010 at 15:55 |

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