×

zbMATH — the first resource for mathematics

Acyclic 4-choosability of planar graphs without adjacent short cycles. (English) Zbl 1252.05041
Summary: The acyclic 4-choosability was proved, in particular, for the following planar graphs: without 3- and 4-cycles [M. Montassier, A. Raspaud and W. Wang, Algorithms and Combinatorics 26, 473–491 (2006; Zbl 1120.05034)], without 4-, 5-, and 6-cycles [M. Montassier et al. (loc. cit.)], either without 4-, 6-, and 7-cycles, or without 4-, 6-, and 8-cycles [M. Chen, A. Raspaud and W. Wang,“Acyclic 4-choosability of planar graphs without prescribed cycles” (to appear)], and with neither 4-cycles nor 6-cycles adjacent to a triangle [O. V. Borodin, A. O. Ivanova and A. Raspaud, Discrete Math. 310, No. 21, 2946–2950 (2010; Zbl 1209.05063)].
There exist planar acyclically non-4-colorable bipartite graphs [A. V. Kostochka and L. S. Mel’nikov, ibid. 14, 403–406 (1976; Zbl 0318.05103)]. This partly explains the fact that in all previously known sufficient conditions for the acyclic 4-choosability of planar graphs the 4-cycles are completely forbidden. In this paper we allow 4-cycles nonadjacent to relatively short cycles; namely, it is proved that a planar graph is acyclically 4-choosable if it does not contain an \(i\)-cycle adjacent to a \(j\)-cycle, where \(3\leq j\leq 6\) if \(i=3\) and \(4\leq j\leq 7\) if \(i=4\). In particular, this absorbs all the above-mentioned results.

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] Albertson, M.O.; Berman, D., Every planar graph has an acyclic 7-coloring, Israel J. math., 28, 169-177, (1977) · Zbl 0374.05022
[2] Borodin, O.V., Proof of B. grünbaum’s conjecture on the acyclic 5-colorability of planar graphs, Dokl. akad. nauk SSSR, 231, 1, 18-20, (1976), (in Russian) · Zbl 0363.05031
[3] Borodin, O.V., On acyclic colorings of planar graphs, Discrete math., 25, 211-236, (1979) · Zbl 0406.05031
[4] 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
[5] 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
[6] Borodin, O.V., Acyclic 4-colorability of planar graphs with neither 4-cycles nor 5-cycles, Diskretn. anal. issled. oper., 17, 2, 20-38, (2010), (in Russian) · Zbl 1249.05109
[7] Borodin, O.V.; Chen, M.; Ivanova, A.O.; Raspaud, A., Acyclic 3-choosability of sparse graphs with girth at least 7, Discrete math., 310, 17-18, 2426-2434, (2010) · Zbl 1213.05049
[8] 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
[9] 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
[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, Sib. math. J., 52, 3, 522-541, (2011), (in Russian) · Zbl 1294.05057
[12] O.V. Borodin, A.O. Ivanova, Acyclic 4-choosability of planar graphs with no 4-and 5-cycles, J. Graph Theory. http://dx.doi.org/10.1002/jgt.21647, published online in 2012. · Zbl 1261.05013
[13] 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
[14] Borodin, O.V.; Kostochka, A.V.; Woodall, D.R., Acyclic colorings of planar graphs with large girth, J. London math. soc., 60, 344-352, (1999) · Zbl 0940.05032
[15] Chen, M.; Raspaud, A., On acyclic 4-choosability of planar graphs without short cycles, Discrete math., 310, 15-16, 2113-2118, (2010) · Zbl 1221.05075
[16] M. Chen, A. Raspaud, A sufficient condition for planar graphs to be acyclically 5-choosable, J. Graph Theory (in press). · Zbl 1242.05089
[17] M. Chen, A. Raspaud, Planar graphs without 4-and 5-cycles are acyclically 4-choosable, Discrete Appl. Math. (in press). · Zbl 1273.05061
[18] M. Chen, A. Raspaud, W. Wang, Acyclic 4-choosability of planar graphs without prescribed cycles (submitted for publication). · Zbl 1221.05075
[19] Chen, M.; Wang, W., Acyclic 5-choosability of planar graphs without 4-cycles, Discrete math., 308, 6216-6225, (2008) · Zbl 1189.05059
[20] Grünbaum, B., Acyclic colorings of planar graphs, Israel J. math., 14, 3, 390-408, (1973) · Zbl 0265.05103
[21] Hell, P.; Nešetřil, J., ()
[22] Hocquard, H.; Montassier, M., Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable, Inform. process. lett., 109, 21-22, 1193-1196, (2009) · Zbl 1197.05050
[23] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley Interscience · Zbl 0971.05046
[24] Kostochka, A.V., Acyclic 6-coloring of planar graphs, Diskret. anal., 28, 40-56, (1976), (in Russian) · Zbl 0412.05043
[25] 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
[26] Mitchem, J., Every planar graph has an acyclic 8-coloring, Duke math. J., 14, 177-181, (1974) · Zbl 0284.05103
[27] Montassier, M., Acyclic 4-choosability of planar graphs with girth at least 5, (), 299-310 · Zbl 1118.05036
[28] Montassier, M.; Ochem, P.; Raspaud, A., On the acyclic choosability of graphs, J. graph theory, 51, 281-300, (2006) · Zbl 1107.05036
[29] Montassier, M.; Raspaud, A.; Wang, W., Acyclic 4-choosability of planar graphs without cycles of specific lengths, (), 473-491 · Zbl 1120.05034
[30] 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
[31] Thomassen, C., Every planar graph is 5-choosable, J. combin. theory ser. B, 62, 180-181, (1994) · Zbl 0805.05023
[32] Voigt, M., List colorings of planar graph, Discrete math., 120, 215-219, (1993) · Zbl 0790.05030
[33] Wang, W.; Chen, M., Planar graphs without 4-cycles are acyclically 6-choosable, J. graph theory, 61, 307-323, (2009) · Zbl 1185.05068
[34] Zhang, H.; Xu, B., Acyclic 5-choosable 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.