# zbMATH — the first resource for mathematics

Defective list colorings of planar graphs. (English) Zbl 0916.05026
A defective coloring with defect $$d$$ is a coloring of the vertices of a graph so that each color class induces a subgraph with maximum degree at most $$d$$. A $$k$$-list assignment $$L$$ is an assignment of sets to vertices such that $$| L(v)|=k$$ for all vertices $$v$$; an $$L$$-list coloring is a coloring having, for each vertex $$v$$, the color of $$v$$ in $$L(v)$$; and a $$d$$-defective $$L$$-list coloring is an $$L$$-list defective coloring with defect $$d$$. Finally, a $$(k,d)$$-choosable graph is $$d$$-defective $$L$$-list colorable for all $$k$$-list assignments $$L$$. The authors show that all planar graphs are (3, 2)-choosable, and that all outerplanar graphs are (2, 2)-choosable. N. Alon and M. Tarsi [Combinatorica 12, No. 2, 125-134 (1992; Zbl 0756.05049)] have shown that all bipartite planar graphs are (3, 0)-choosable. The present authors show that all three results are best possible. They also show that all triangle-free outerplanar graphs are (2, 1)-choosable.

##### MSC:
 05C15 Coloring of graphs and hypergraphs
##### Keywords:
defective coloring; defect; planar graphs; outerplanar graphs