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 ICA 25 (1999) 79-87

[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., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu (with thanks to Doug Woodall)

November, 2003