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

##### MSC:
 05C15 Coloring of graphs and hypergraphs 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles
##### Keywords:
combinatorial problems; coloring; list-coloring; choosability
Full Text:
##### References:
  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  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  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  Grötzsch, H., Ein dreifarbensatz für dreikreisfreie netze auf der kugel, Math.-nat. reihe, 8, 109-120, (1959)  Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley Interscience New York · Zbl 0971.05046  Thomassen, C., 3-List coloring planar graphs of girth 5, J. combin. theory, ser. B, 64, 101-107, (1995) · Zbl 0822.05029  Voigt, M., A not 3-choosable planar graph without 3-cycles, Discrete math., 146, 325-328, (1995) · Zbl 0843.05034  M. Voigt, A non-3-choosable planar graph without cycles of length 4 and 5, 2003, Manuscript · Zbl 1112.05041  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.