Thomassen, Carsten 3-list-coloring planar graphs of girth 5. (English) Zbl 0822.05029 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) Cited in 9 ReviewsCited in 71 Documents MSC: 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory Keywords:list coloring; planar graph PDF BibTeX XML Cite \textit{C. Thomassen}, J. Comb. Theory, Ser. B 64, No. 1, 101--107 (1995; Zbl 0822.05029) Full Text: DOI OpenURL