**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.

**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.,

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