×

zbMATH — the first resource for mathematics

Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable. (English) Zbl 1228.05131
Summary: It is shown that a planar graph without cycles of length 4, 5, 8, or 9 is 3-choosable.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N.; Tarsi, M., Colorings and orientations of graphs, Combinatorica, 12, 2, 125-134, (1992) · Zbl 0756.05049
[2] Borodin, O.V.; Glebov, A.N.; Raspaud, A.; Salavatipour, M.R., Planar graphs without cycles of length from 4 to 7 are 3-colorable, J. combin. theory ser. B, 93, 303-311, (2005) · Zbl 1056.05052
[3] Erdös, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)
[4] Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 119-130, (1996) · Zbl 0865.05066
[5] Lam, P.; Shiu, W.C.; Song, Z.M., The 3-choosability of plane graphs of girth 4, Discrete math., 294, 297-301, (2005) · Zbl 1062.05061
[6] Montassier, M.; Raspaud, A.; Wang, W., Bordeaux 3-color conjecture and 3-choosability, Discrete math., 306, 573-579, (2006) · Zbl 1090.05029
[7] Montassier, M., A note on the not 3-choosability of some families of planar graphs, Inform. process. lett., 99, 68-71, (2006) · Zbl 1184.05048
[8] Shen, L.; Wang, Y., A sufficient condition for a planar graph to be 3-choosable, Inform. process. lett., 104, 146-151, (2007) · Zbl 1183.05022
[9] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[10] Thomassen, C., 3-List coloring planar graphs of girth 5, J. combin. theory ser. B, 64, 101-107, (1995) · Zbl 0822.05029
[11] Voigt, M., List colourings of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
[12] Voigt, M., A non-3-choosable planar graph without cycles of length 4 and 5, Discrete math., 307, 1013-1015, (2007) · Zbl 1112.05041
[13] Wang, W.; Chen, M., On 3-colorable planar graphs without prescribed cycles, Discrete math., 307, 2820-2825, (2007) · Zbl 1128.05025
[14] Wang, Y.; Chen, M.; Shen, L., Plane graphs without cycles of length 4, 6, 7 or 8 are 3-colorable, Discrete math., 308, 4014-4017, (2008) · Zbl 1203.05060
[15] Y. Wang, L. Shen, Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable (in manuscript) · Zbl 1210.05029
[16] Wang, Y.; Lu, H.; Chen, M., A note on 3-choosability of planar graphs, Inform. process. lett., 105, 206-211, (2008) · Zbl 1183.05023
[17] Xu, B., On 3-colorable plane graphs without 5- and 7-cycles, J. combin. theory ser. B, 96, 958-963, (2006) · Zbl 1108.05046
[18] Zhang, L.; Wu, B., Three-coloring planar graphs without certain small cycles, Graph theory notes of N. Y., 46, 27-30, (2004)
[19] 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.