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.

05C15 Coloring of graphs and hypergraphs