Defective List Colorings

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. The analogous conjecture is false for list colorings since there exist planar graphs that are not 4-choosable. Gravier [G] has shown that forbidding complete bipartite minors might play a similar role for list colorings. This leads to the following two conjectures from [W] (the first is strictly weaker than Hadwiger's Conjecture).

Conjecture: Every K_{r,s}-minor-free graph is (r+s-1) colorable.

Conjecture: Every K_{r,s}-minor-free graph is (r+s-1) 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. The following are analogues of the previous conjectures for defective colorings

Conjecture: Every K_{r,s}-minor-free graph is (r+s-1-d,d) colorable for every d at most s-1.

Conjecture: Every K_{r,s}-minor-free graph is (r+s-1-d,d) choosable for every d at most s-1.

A very good survey on list colorings is given by Woodall [W]. In particular, he proves these four conjectures when r is at most 2.

References:

[G] S. Gravier, A Hajos-like theorem for list coloring, Discrete Math. 152 (1996) 299-302.

[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