3-Choosability of Planar Graphs

A list-assignment L gives a list of colors available at each vertex. Commonly the size k of the list is independent on the vertices, and we talk about a k-list assignment. An L-coloring assigns each vertex one of the colors in its list. Usually we want proper colorings, so that adjacent vertices receive distinct colors. The list-chromatic number is the smallest k such that every k-list assignment L has a proper L-coloring. Obviously, the list chromatic number is greater than or equal to the chromatic number, since the latter is the special case that all vertices get lists 1,...,k. A graph with list-chromatic number at least k is also called k-choosable.

Steinberg [S] asks:

Problem: If G is a planar graph without 4-cycles and 5-cycles, is G 3-choosable?

It is known that planar graphs of girth at least 5 are 3-choosable. It was claimed that planar graphs of girth 4 were 3-choosable [LS,LSS], but a counterexample is known [V]. Planar graphs without 5-cycles are 4-choosable [LW].


[LW] K. Lih and W. Wang, The 4-choosability of planar graphs without 5-cycles, preprint.

[LS] Z. Song and P.C.B. Lam, The 3-choosability of triangle-free plane graphs, preprint

[LSS] P.C.B. Lam, W.C. Shiu, and Z. Song, 3-choosability of plane graphs of girth 4, preprint

[S] R. Steinberg, The state of the three color problem, preprint

[V] M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325-328

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003