zbMATH — the first resource for mathematics

A not 3-choosable planar graph without 3-cycles. (English) Zbl 0843.05034
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 [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 [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.

MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles
Keywords:
choosability; coloring; planar graph
Full Text:
References:
 [1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 125-134, (1992) · Zbl 0756.05049 [2] Erdős, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, () [3] Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, (), 109-119 [4] J. Kratochvil and Z. Tuza, Algorithmic complexity of list coloring, Discrete Appl. Math., to appear. · Zbl 0807.68055 [5] Mahadev, N.V.R.; Roberts, F.S.; Santhanakrishnan, P., 3-choosable complete bipartite graphs, DIMACS, tech. report 91-62, (1991) [6] Roberts, F.S., From garbage to rainbows, generalizations of graphs coloring and their applications, RUTCOR research report 36-88, (July 1988) [7] Roberts, F.S., New directions in graph theory, () · Zbl 0193.24301 [8] Thomassen, C., Every planar graph is 5-choosable, () · Zbl 0805.05023 [9] Thomassen, C., 3-List-coloring planar graphs of girth 5, () · Zbl 0822.05029 [10] Vizing, V.G.; Vizing, V.G., Coloring the vertices of a graph in prescribed colors, Diskret. analiz no. 29 metody diskret. anal. v teorii kodov i shem, Diskret. analiz no. 29 metody diskret. anal. v teorii kodov i shem, 101-10, (1976), (in Russian) · Zbl 1249.90303 [11] Voigt, M., List colourings of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.