A not 3-choosable planar graph without 3-cycles (Q1903746): Difference between revisions

A graph \(G\) is \(k\)-choosable if for every list assignment \(v\mapsto L(v)\), where \(L(v)\) is a \(k\)-set \((v\in V(G))\), \(G\) admits a proper coloring such that the color of each vertex \(v\) belongs to \(L(v)\). Thomassen strengthened the 5-color theorem by showing that every planar graph is 5-choosable [\textit{C. Thomassen}, Every planar graph is 5-choosable, J. Comb. Theory, Ser. B 62, No. 1, 180-181 (1994; Zbl 0805.05023)]. Grötzsch proved that every triangle-free planar graph \(G\) admits a 3-coloring, and Thomassen strengthened it to 3-choosability under the stronger condition that the girth of \(G\) is 5 [\textit{C. Thomassen}, 3-list-coloring planar graphs of girth 5, J. Comb. Theory, Ser. B 64, No. 1, 101-107 (1995; Zbl 0822.05029)]. In this paper it is proved that there exists a planar graph of girth 4 which is not 3-choosable.