zbMATH — the first resource for mathematics

A note on the not 3-choosability of some families of planar graphs. (English) Zbl 1184.05048
Summary: A graph \(G\) is \(L\)-list colorable if for a given list assignment \(L = \{L(v): v\in V\}\), there exists a proper coloring \(c\) of \(G\) such that \(c(v) \in L(v)\) for all \(v\in V\). If \(G\) is \(L\)-list colorable for any list assignment with \(|L(v)| \geqslant k\) for all \(v\in V\), then \(G\) is said \(k\)-choosable. In [M. Voigt, “A not 3-choosable planar graph without 3-cycles”, Discrete Math. 146, No. 1-3, 325–328 (1995; Zbl 0843.05034)] and [M. Voigt, “A non-3-choosable planar graph without cycles of length 4 and 5”, Discrete Math. 307, No. 7-8, 1013–1015 (2007; Zbl 1112.05041)], Voigt gave a planar graph without 3-cycles and a planar graph without 4-cycles and 5-cycles which are not 3-choosable. In this note, we give smaller and easier graphs than those proposed by Voigt and suggest an extension of Erdős’ relaxation of Steinberg’s conjecture to 3-choosability.

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
Full Text: DOI
[1] Borodin, O.V., Structural properties of plane graphs without adjacent triangles and an application to 3-colorings, J. graph theory, 21, 2, 183-186, (1996) · Zbl 0838.05039
[2] Borodin, O.V.; Glebov, A.N.; Raspaud, A.; Salavatipour, M.R., Planar graphs without cycles of length 4 to 7 are 3-colorable, J. combin. theory, ser. B, 93, 303-311, (2005) · Zbl 1056.05052
[3] Glebov, A.N.; Kostochka, A.V.; Tashkinov, V.A., Smaller planar triangle-free graphs that are not 3-List-colorable, Discrete math., 290, 269-274, (2005) · Zbl 1058.05022
[4] Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, Math.-nat. reihe, 8, 109-120, (1959)
[5] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley Interscience New York · Zbl 0971.05046
[6] Thomassen, C., 3-List coloring planar graphs of girth 5, J. combin. theory, ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[7] Voigt, M., A not 3-choosable planar graph without 3-cycles, Discrete math., 146, 325-328, (1995) · Zbl 0843.05034
[8] M. Voigt, A non-3-choosable planar graph without cycles of length 4 and 5, 2003, Manuscript · Zbl 1112.05041
[9] Zhang, L.; Wu, B., A note on 3-choosability of planar graphs without certain cycles, Discrete math., 297, 206-209, (2005) · Zbl 1070.05046
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.