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].
Submitted by: Dan Archdeacon, Dept. of Math.
Send comments to firstname.lastname@example.org