This article is cited in 8 scientific papers (total in 8 papers)
Acyclic 5-choosability of planar graphs without 4-cycles
O. V. Borodinab, A. O. Ivanovac
a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University, Novosibirsk
c Institute for Mathematics and Informatics, Yakutsk State University, Yakutsk
The conjecture on the acyclic 5-choosability of planar graphs (Borodin et al., 2002) as yet has been verified only for several restricted classes of graphs: those of girth at least 5 (Montassier, Ochem, and Raspaud, 2006), without 4- and 5-cycles or without 4- and 6-cycles (Montassier, Raspaud, and Wang, 2007), with neither 4-cycles nor chordal 6-cycles (Zhang and Xu, 2009), with neither 4- cycles nor two 3-cycles at distance less than 3 (Chen and Wang, 2008), and with neither 4-cycles nor intersecting 3-cycles (Chen and Raspaud, 2010). Wang and Chen (2009) proved that the planar graphs without 4-cycles are acyclically 6-choosable. We prove that a planar graph without 4-cycles is acyclically 5-choosable, which is a common strengthening of all above-mentioned results.
graph, planar graph, coloring, acyclic coloring, list coloring.
PDF file (455 kB)
Siberian Mathematical Journal, 2011, 52:3, 411–425
O. V. Borodin, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Sibirsk. Mat. Zh., 52:3 (2011), 522–541; Siberian Math. J., 52:3 (2011), 411–425
Citation in format AMSBIB
\by O.~V.~Borodin, A.~O.~Ivanova
\paper Acyclic 5-choosability of planar graphs without 4-cycles
\jour Sibirsk. Mat. Zh.
\jour Siberian Math. J.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
Borodin O.V., Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs Without Adjacent Short Cycles”, Discrete Math., 312:22 (2012), 3335–3341
Borodin O.V., Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs with No 4- and 5-Cycles”, J. Graph Theory, 72:4 (2013), 374–397
Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539
Chen M., Raspaud A., “Planar Graphs Without 4-and 5-Cycles Are Acyclically 4-Choosable”, Discrete Appl. Math., 161:7-8 (2013), 921–931
Wang WeiFan, Zhang Ge, Chen Min, “Acyclic 6-Choosability of Planar Graphs Without Adjacent Short Cycles”, Sci. China-Math., 57:1 (2014), 197–209
Cranston D.W., West D.B., “An Introduction to the Discharging Method Via Graph Coloring”, Discrete Math., 340:4 (2017), 766–793
Sun Y., Chen M., Chen D., “Acyclic 4-Choosability of Planar Graphs Without Intersecting Short Cycles”, Discret. Math. Algorithms Appl., 10:1 (2018), 1850014
Sun L., “A Sufficient Condition For Acyclic 5-Choosability of Planar Graphs Without 5-Cycles”, Bull. Korean. Math. Soc., 55:2 (2018), 415–430
|Number of views:|