3-list-coloring planar graphs of girth 5. (English) Zbl 0822.05029

Thomassen, Carsten

J. Comb. Theory, Ser. B 64, No. 1, 101-107 (1995).

If each vertex of a graph \(G\) is assigned a list \(L(v)\) of natural numbers, then a list coloring of \(G\) is a map from \(V(G)\) to \(\mathbb{N}\) such that each \(v\) is mapped into \(L(v)\) and adjacent vertices always receive distinct numbers (colors). Then \(G\) is \(k\)-choosable if \(G\) has a list coloring for each list assignment with \(k\) colors in each list, and \(k\)- colorable if \(G\) has a list coloring with all lists being \(\{1, 2, 3,\dots, k\}\). The author proves, using only vertex deletion and induction, that every planar graph of girth at least 5 is 3-choosable, even with the precoloring of any 5-cycle. This extension allows an immediate proof of Grötzsch’s theorem that every planar graph of girth at least 4 is 3-colorable.

Reviewer: A.T.White (Kalamazoo)

MSC:

05C15	Coloring of graphs and hypergraphs
05C10	Planar graphs; geometric and topological aspects of graph theory

Keywords:

list coloring; planar graph