3-list-coloring planar graphs of girth 5 (Q1892853): Difference between revisions

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.