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

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.


05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI