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:
[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