×

zbMATH — the first resource for mathematics

Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable. (English) Zbl 1210.05029
Summary: It is known that planar graphs without cycles of length 4, \(i, j\), or 9 with \(4<i<j<9\), except that \(i=7\) and \(j=8\), are 3-choosable. This paper proves that planar graphs without cycles of length 4, 7, 8, or 9 are also 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] Erdös, P.; Rubin, A.L.; Taylor, H., Choosability in graphs, Congr. numer., 26, 125-157, (1979)
[2] Gutner, S., The complexity of planar graph choosability, Discrete math., 159, 119-130, (1996) · Zbl 0865.05066
[3] 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
[4] 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
[5] Thomassen, C., Every planar graphs is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[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., List colourings of planar graphs, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
[8] Wang, Y.; Lu, H.; Chen, M., A note on 3-choosability of planar graphs, Inform. process. lett., 105, 206-211, (2008) · Zbl 1183.05023
[9] Wang, Y.; Lu, H.; Chen, M., Plane graphs without cycles of length 4, 5, 8 or 9 are 3-choosable, Discrete math., 310, 147-158, (2010) · Zbl 1228.05131
[10] Zhang, L.; Wu, B., Three-coloring planar graphs without certain small cycles, Graph theory notes NY, 46, 27-30, (2004)
[11] 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.