This article is cited in 13 scientific papers (total in 13 papers)
Acyclic 3-choosability of plane graphs without cycles of length from 4 to 12
O. V. Borodin
S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
Every planar graph is known to be acyclically 7-choosable and is conjectured to be acyclically 5-choosable (Borodin et al., 2002). This conjecture, if proved, would imply both Borodin's acyclic 5-color theorem (1979) and Thomassen's 5-choosability theorem (1994). However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4- and 3-choosable. In particular, a planar graph of girth at least 7 is acyclically 3-colorable (Borodin, Kostochka, and Woodall, 1999) and acyclically 3-choosable (Borodin et al., 2009).
A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of $k$-cycles, where $4\le k\le S$. Here, we prove that every planar graph with no cycles with length from 4 to 12 is acyclically 3-choosable. Bibl. 18.
planar graph, acyclic coloring, acyclic choosability.
PDF file (235 kB)
Journal of Applied and Industrial Mathematics, 2010, 4:2, 158–162
O. V. Borodin, “Acyclic 3-choosability of plane graphs without cycles of length from 4 to 12”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 26–33; J. Appl. Industr. Math., 4:2 (2010), 158–162
Citation in format AMSBIB
\paper Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12
\jour Diskretn. Anal. Issled. Oper.
\jour J. Appl. Industr. Math.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
O. V. Borodin, “Acyclic 4-coloring of plane graphs without cycles of length 4 and 6”, J. Appl. Industr. Math., 4:4 (2010), 490–495
O. V. Borodin, “Acyclic 4-colorability of planar graphs without 4- and 5-cycles”, J. Appl. Industr. Math., 5:1 (2011), 31–43
O. V. Borodin, A. O. Ivanova, “Acyclic $3$-choosability of planar graphs with no cycles of length from $4$ to $11$”, Sib. elektron. matem. izv., 7 (2010), 275–283
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:21 (2010), 2946–2950
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 (2010), 2426–2434
Hocquard H., Montassier M., Raspaud A., “A note on the acyclic 3-choosability of some planar graphs”, Discrete Appl. Math., 158:10 (2010), 1104–1110
O. V. Borodin, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Siberian Math. J., 52:3 (2011), 411–425
Borodin O.V., Ivanova A.O., “Acyclic 5-choosability of planar graphs without adjacent short cycles”, J. Graph Theory, 68:2 (2011), 169–176
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
Yan H., Qi H., “3-Paintability of Planar Graphs”, Discret. Math. Algorithms Appl., 10:5 (2018), 1850067
|Number of views:|