General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Diskretn. Anal. Issled. Oper.:

Personal entry:
Save password
Forgotten password?

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

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

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 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.

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
Received: 13.05.2009
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
\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
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 2
\pages 158--162

Linking options:

    SHARE: FaceBook Twitter Livejournal

    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  mathnet  crossref  mathscinet  zmath
    2. O. V. Borodin, “Acyclic 4-colorability of planar graphs without 4- and 5-cycles”, J. Appl. Industr. Math., 5:1 (2011), 31–43  mathnet  crossref  mathscinet  zmath
    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  mathnet
    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  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    7. O. V. Borodin, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Siberian Math. J., 52:3 (2011), 411–425  mathnet  crossref  mathscinet  isi
    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  crossref  mathscinet  zmath  isi  elib  scopus
    9. Borodin O.V. Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs Without Adjacent Short Cycles”, Discrete Math., 312:22 (2012), 3335–3341  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    11. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib  scopus
    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  crossref  mathscinet  zmath  isi  elib  scopus
    13. Yan H., Qi H., “3-Paintability of Planar Graphs”, Discret. Math. Algorithms Appl., 10:5 (2018), 1850067  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:390
    Full text:68
    First page:3

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020