×

zbMATH — the first resource for mathematics

Planar graphs without 4- and 5-cycles are acyclically 4-choosable. (English) Zbl 1262.05029
Summary: Let \(G=(V,E)\) be a graph. A proper vertex coloring of \(G\) is acyclic if \(G\) contains no bicolored cycle. Namely, every cycle of \(G\) must be colored with at least three colors. \(G\) is acyclically \(L\)-list colorable if for a given list assignment \(L=\{ L(v) : v \in V\} \), there exists a proper acyclic coloring \(\pi\) of \(G\) such that \(\pi (v)\in L(v)\) for all \(v\in V\) . If \(G\) is acyclically \(L\)-list colorable for any list assignment with \(|L(v)|\geq k\) for all \(v\in V\), then \(G\) is acyclically \(k\)-choosable.
T. R. Jensen and B. Toft [Graph coloring problems. New York, NY: John Wiley & Sons (1995; Zbl 0855.05054)] conjectured that every planar graph without 4- and 5-cycles is 3-colorable. This conjecture cannot be improved to 3-choosability basing on the examples given by M. Voigt [Discrete Math. 307, No. 7–8, 1013–1015 (2007; Zbl 1112.05041)] and, independently, by M. Montassier [“A smaller not 3-choosable planar graph without 4- and 5-cycles”. Research Report RR-1361-05 (2005)].
In this paper, we prove that planar graphs without 4- and 5-cycles are acyclically 4-choosable. This result (obtained independently by O. V. Borodin and A. O. Ivanova [J. Graph Theory 72, No. 3–4, 374–397 (2013; Zbl 1261.05013)]) is also a new approach to the conjecture proposed by M. Montassier et al. [Algorithms and Combinatorics 26, 473–491 (2006; Zbl 1120.05034)], which says that every planar graph without 4-cycles is acyclically 4-choosable.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Albertson, M. O.; Berman, D. M., Every planar graph has an acyclic 7-coloring, Israel J. Math., 28, 169-174, (1977) · Zbl 0374.05022
[2] Borodin, O. V., On acyclic coloring of planar graphs, Discrete Math., 25, 211-236, (1979) · Zbl 0406.05031
[3] Borodin, O. V., Acyclic 3-choosability of planar graphs without cycles of length from 4 to 12, Diskretn. Anal. Issled. Oper., 16, 5, 26-33, (2009), (in Russian) · Zbl 1249.05107
[4] Borodin, O. V., Acyclic 4-colorability of planar graphs without 4- and 6-cycles, Diskretn. Anal. Issled. Oper., 16, 6, 3-11, (2009), (in Russian) · Zbl 1249.05108
[5] Borodin, O. V., Acyclic 4-colorability of planar graphs without 4- and 5-cycles, Diskretn. Anal. Issled. Oper., 17, 2, 20-38, (2010), (in Russian) · Zbl 1249.05109
[6] Borodin, O. V.; Chen, M.; Ivanova, A. O.; Raspaud, A., Acyclic 3-choosability of sparse graphs with girth at least 7, Discrete Math., 310, 2426-2434, (2010) · Zbl 1213.05049
[7] Borodin, O. V.; Fon-Der Flaass, D. G.; Kostochka, A. V.; Raspaud, A.; Sopena, E., Acyclic List 7-coloring of planar graphs, J. Graph Theory, 40, 83-90, (2002) · Zbl 1004.05029
[8] Borodin, O. V.; Ivanova, A. O., Acyclic 3-choosability of planar graphs with no cycles of length from 4 to 11, Sib. Élektron. Mat. Izv., 7, 275-283, (2010) · Zbl 1329.05101
[9] Borodin, O. V.; Ivanova, A. O., Acyclic 4-choosability of planar graphs with no 4- and 5-cycles, J. Graph Theory., (2012) · Zbl 1252.05041
[10] Borodin, O. V.; Ivanova, A. O., Acyclic 5-choosability of planar graphs without adjacent short cycles, J. Graph Theory, 68, 2, 169-176, (2011) · Zbl 1235.05038
[11] Borodin, O. V.; Ivanova, A. O., Acyclic 5-choosability of planar graphs without 4-cycles, Sibirsk. Mat. Zh., 52, 3, 522-541, (2011), (in Russian) · Zbl 1294.05057
[12] Borodin, O. V.; Ivanova, A. O.; Raspaud, A., Acyclic 4-choosability of planar graphs with neither 4-cycles nor triangular 6-cycles, Discrete Math., 310, 2946-2950, (2010) · Zbl 1209.05063
[13] Borodin, O. V.; Kostochka, A. V.; Woodall, D. R., Acyclic colourings of planar graphs with large girth, J. Lond. Math. Soc., 2, 60, 344-352, (1999) · Zbl 0940.05032
[14] Chen, M.; Raspaud, A., On acyclic 4-choosability of planar graphs without short cycles, Discrete Math., 310, 2113-2118, (2010) · Zbl 1221.05075
[15] Chen, M.; Raspaud, A., A sufficient condition for planar graphs to be acyclically 5-choosable, J. Graph Theory, 70, 135-151, (2012) · Zbl 1242.05089
[16] Chen, M.; Raspaud, A.; Roussel, N.; Zhu, X., Acyclic 4-choosability on planar graphs, Discrete Math., 311, 92-101, (2011) · Zbl 1216.05028
[17] Chen, M.; Wang, W., Acyclic 5-choosability of planar graphs without 4-cycles, Discrete Math., 308, 6216-6225, (2008) · Zbl 1189.05059
[18] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. Math., 14, 390-408, (1973) · Zbl 0265.05103
[19] Hocquard, H.; Montassier, M., Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable, Inform. Process. Lett., 109, 1193-1196, (2009) · Zbl 1197.05050
[20] Jensen, T. R.; Toft, B., Graph coloring problems, (1995), Wiley-Interscience New York · Zbl 0855.05054
[21] Kostochka, A. V., Acyclic 6-coloring of planar graphs, Metody Diskret. Anal., 28, 40-56, (1976), (in Russian) · Zbl 0412.05043
[22] Kostochka, A. V.; Mel’nikov, L. S., Note to the paper of grünbaum on acyclic colorings, Discrete Math., 14, 403-406, (1976) · Zbl 0318.05103
[23] Mitchem, J., Every planar graph has an acyclic 8-coloring, Duke Math. J., 41, 177-181, (1974) · Zbl 0284.05103
[24] M. Montassier, A smaller not 3-choosable planar graph without 4- and 5-cycles, Research Report RR-1361-05, 2005.
[25] Montassier, M., Acyclic 4-choosability of planar graphs with girth at least 5, (Trends in Mathematics: Graph Theory in Paris, (2007)), 299-310 · Zbl 1118.05036
[26] Montassier, M.; Ochem, P.; Raspaud, A., On the acyclic choosability of graphs, J. Graph Theory, 51, 281-300, (2006) · Zbl 1107.05036
[27] Montassier, M.; Raspaud, A.; Wang, W., Acyclic 4-choosability of planar graphs without cycles of specific lengths, (Topics in Discrete Mathematics, Algorithms Combin., vol. 26, (2006), Springer Berlin), 473-491 · Zbl 1120.05034
[28] Montassier, M.; Raspaud, A.; Wang, W., Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory, 54, 245-260, (2007) · Zbl 1114.05037
[29] Thomassen, C., Every planar graph is 5-choosable, J Combin. Theory Ser B, 62, 180-181, (1994) · Zbl 0805.05023
[30] Voigt, M., A non-3-choosable planar graph without cycles of length 4 and 5, Discrete Math., 307, 1013-1015, (2007) · Zbl 1112.05041
[31] Wang, W.; Chen, M., Planar graphs without 4-cycles are acyclically 6-choosable, J. Graph Theory, 61, 289-306, (2009) · Zbl 1185.05068
[32] Zhang, H.; Xu, B., Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles, Discrete Math., 309, 20, 6087-6091, (2009) · Zbl 1204.05049
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.