**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].

**References:**

[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

[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.,

Send comments to *dan.archdeacon@uvm.edu*

December 2003