RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., 2009, Volume 16, Number 5, Pages 26–33 (Mi da584)

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

Abstract: 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 Erdő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.

Keywords: planar graph, acyclic coloring, acyclic choosability.

Full text: PDF file (235 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2010, 4:2, 158–162

Bibliographic databases:

UDC: 519.172.2
Revised: 17.06.2009

Citation: 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
\Bibitem{Bor09} \by O.~V.~Borodin \paper Acyclic 3-choosability of plane graphs without cycles of length from~4 to~12 \jour Diskretn. Anal. Issled. Oper. \yr 2009 \vol 16 \issue 5 \pages 26--33 \mathnet{http://mi.mathnet.ru/da584} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2590752} \zmath{https://zbmath.org/?q=an:1249.05107} \transl \jour J. Appl. Industr. Math. \yr 2010 \vol 4 \issue 2 \pages 158--162 \crossref{https://doi.org/10.1134/S1990478910020031} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77953484802} 

• http://mi.mathnet.ru/eng/da584
• http://mi.mathnet.ru/eng/da/v16/i5/p26

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. 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
2. O. V. Borodin, “Acyclic 4-colorability of planar graphs without 4- and 5-cycles”, J. Appl. Industr. Math., 5:1 (2011), 31–43
3. 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
4. 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
5. 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
6. 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
7. O. V. Borodin, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Siberian Math. J., 52:3 (2011), 411–425
8. Borodin O.V., Ivanova A.O., “Acyclic 5-choosability of planar graphs without adjacent short cycles”, J. Graph Theory, 68:2 (2011), 169–176
9. Borodin O.V. Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs Without Adjacent Short Cycles”, Discrete Math., 312:22 (2012), 3335–3341
10. 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
11. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539
12. Chen M. Raspaud A., “Planar Graphs Without 4-and 5-Cycles Are Acyclically 4-Choosable”, Discrete Appl. Math., 161:7-8 (2013), 921–931
13. Yan H., Qi H., “3-Paintability of Planar Graphs”, Discret. Math. Algorithms Appl., 10:5 (2018), 1850067
•  Number of views: This page: 390 Full text: 68 References: 54 First page: 3