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

 Sib. Èlektron. Mat. Izv.: Year: Volume: Issue: Page: Find

 Sib. Èlektron. Mat. Izv., 2010, Volume 7, Pages 275–283 (Mi semr244)

Research papers

Acyclic $3$-choosability of planar graphs with no cycles of length from $4$ to $11$

O. V. Borodinab, A. O. Ivanovac

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University
c Institute of Mathematics at Yakutsk State University

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., 2010). A natural measure of sparseness, introduced by Erdős and Steinberg, is the absence of $k$-cycles, where $4\le k\le C$. Here, we prove that every planar graph with no cycles of length from $4$ to $11$ is acyclically $3$-choosable.

Keywords: acyclic coloring, planar graph, forbidden cycles.

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

Document Type: Article
UDC: 519.172
MSC: 05C15
Received August 9, 2010, published September 17, 2010
Language: English

Citation: O. V. Borodin, A. O. Ivanova, “Acyclic $3$-choosability of planar graphs with no cycles of length from $4$ to $11$”, Sib. Èlektron. Mat. Izv., 7 (2010), 275–283

Citation in format AMSBIB
\Bibitem{BorIva10} \by O.~V.~Borodin, A.~O.~Ivanova \paper Acyclic $3$-choosability of planar graphs with no cycles of length from~$4$ to~$11$ \jour Sib. \Elektron. Mat. Izv. \yr 2010 \vol 7 \pages 275--283 \mathnet{http://mi.mathnet.ru/semr244} `

• http://mi.mathnet.ru/eng/semr244
• http://mi.mathnet.ru/eng/semr/v7/p275

 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, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Siberian Math. J., 52:3 (2011), 411–425
2. Chen M., Raspaud A., Roussel N., Zhu X., “Acyclic 4-choosability of planar graphs”, Discrete Math., 311:1 (2011), 92–101
3. Borodin O.V., Ivanova A.O., “Acyclic 5-choosability of planar graphs without adjacent short cycles”, J. Graph Theory, 68:2 (2011), 169–176
4. Borodin O.V., Ivanova A.O., “List 2-facial 5-colorability of plane graphs with girth at least 12”, Discrete Math., 312:2 (2012), 306–314
5. Borodin O.V., Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs Without Adjacent Short Cycles”, Discrete Math., 312:22 (2012), 3335–3341
6. 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
7. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539
8. Chen M., Raspaud A., “Planar Graphs Without 4-and 5-Cycles Are Acyclically 4-Choosable”, Discrete Appl. Math., 161:7-8 (2013), 921–931
•  Number of views: This page: 214 Full text: 40 References: 25