Defective List Colorings
of Planar Graphs
A k-list assignment L gives a set of k colors available at each vertex. An L-coloring selects a color from each vertex's list so that adjacent vertices receive different colors. A graph is k-choosable if every k-list assignment has such a coloring.
A graph H is a minor
of G if we can form H from G by a sequence of edge
deletions, edge contractions, and the deletion of isolated vertices. Hadwiger's
Conjecture asserts that if G does not contain a K_{k+1} minor, then G is
k-colorable. Note that the case k=4 is equivalent to the Four-Color-Theorem.
We are concerned with the choice number of planar graphs. Voigt [V] has given a
planar graph that is not 4-choosable. Thomassen [T] has shown that every planar
graph is 5-choosable. More strongly, Skrekovski [S1] has shown that every
K_5-minor-free graph is 5-choosable.
The defect, d, of a non-proper coloring is the maximum degree in the subgraphs of fixed colors. In other words, a coloring has defect d if no vertex is adjacent to greater than d other vertices of the same color. Hence having defect 0 is equivalent to a proper coloring. Combining the previous two concepts, we say that a graph is (k,d)-choosable if every k-list function has a list coloring of defect d. Skrekovski [S2] has shown that every planar graph is (3,2)-choosable. The following three conjectures are still open; either of the latter two imply the first.
Conjecture: Every planar graph is (4,1)-choosable.
Conjecture: Every K_5-minor-free
graph is (4,1)-choosable.
Conjecture: Every K_{3,3}-minor-free graph is (4,1)-choosable.
A very good survey on list colorings is given by Woodall [W]. Other good articles are [EH] and [CGJ].
References:
[CGJ] L. Cowen, W. Goddard, and C.E.
Jerurum, Defective colorings revisited, J. of Graph Theory 24 (1997)
205-220
[EH] N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull.
of the
[S1] R. Skrekovski, Choosability of K_5-minor-free graphs, Discrete Math. 190 (1998) 223-226
[S1] R. Skrekovski, List improper colourings of planar graphs, Combin. Prob. Comput.. 8 (1999) 292-299
[T] C. Thomassen, Every planar graph is 5-choosable, J. Combin. Theory Ser. B 62 (1994) 180-181
[V] M. Voigt, List colorings of planar graphs, Discrete Math. 120 (1993) 215-219
[W] D.R. Woodall, List colourings of graphs, 269-301
Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,
Send comments to dan.archdeacon@uvm.edu (with thanks to Doug Woodall)
November, 2003