On 3-colorable non-4-choosable planar graphs. (English) Zbl 0868.05025

An \(L\)-list coloring for a graph \(G\) is a proper vertex coloring for which every vertex \(v\) gets its color from a list \(L(v)\) of allowable colors. Then \(G\) is \(k\)-choosable if each list has exactly \(k\) elements and if \(G\) is \(L\)-list colorable for all possible arrangements of such lists. It is known that every planar graph is 5-choosable (see C. Thomassen [J. Comb. Theory, Ser. B 62, No. 1, 180-181 (1994; Zbl 0805.05023)]) and that there are planar graphs which are not 4-choosable (see the first author [Discrete Math. 120, No. 1-3, 215-219 (1993; Zbl 0790.05030)]). Voigt’s graph has more than 200 vertices. S. Gutner [Discrete Math. 159, No. 1-3, 119-130 (1996; Zbl 0865.05066)] gives a non-4-choosable planar graph on 74 vertices. In the present note, the authors show that Gutner’s graph is 3-colorable, and they give a list assignment for the graph, using altogether five colors (four available at each vertex), so that it is not list-colorable. The latter is best possible, in the sense that if the same four colors are available at each vertex, then the 4-color theorem guarantees a proper coloring.


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