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

### Citations:

Zbl 0805.05023; Zbl 0822.05029
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, (Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing. Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Arcata, CA. Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing. Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Arcata, CA, Congressus Numeratium XXVI (5-7 September 1979)) [3] Grötzsch, H., Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, (Math.-nat. VIII/1 (1958), Wiss. Zeitschrift der Universität Halle), 109-119 [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, (Quo vadis, Graph Theory?. Quo vadis, Graph Theory?, Ann. Discrete Math., 55 (1993)) · Zbl 0193.24301 [8] Thomassen, C., Every planar graph is 5-choosable, (MAT-REPORT No. 1993-24 (1993), Mathematical Institut, The Technical University of Denmark: Mathematical Institut, The Technical University of Denmark Lyngby) · Zbl 0805.05023 [9] Thomassen, C., 3-List-coloring planar graphs of girth 5, (MAT-REPORT No. 1994-12 (1994), Mathematical Institut, The Technical University of Denmark: Mathematical Institut, The Technical University of Denmark Lyngby) · Zbl 0822.05029 [10] Vizing, V. G., Coloring the vertices of a graph in prescribed colors, Diskret. Analiz No. 29 Metody Diskret. Anal. v Teorii Kodov i Shem, 101 (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.