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

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

November, 2003