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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
\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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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
    References:54
    First page:3

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