## 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.

### MSC:

 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory

### Keywords:

vertex coloring; planar graph; list-colorable; 865

### Citations:

Zbl 0805.05023; Zbl 0790.05030; Zbl 0865.05066
Full Text: