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






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


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

This article is cited in 8 scientific papers (total in 8 papers)

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 Erdő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. È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}


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

    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, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Siberian Math. J., 52:3 (2011), 411–425  mathnet  crossref  mathscinet  isi
    2. Chen M., Raspaud A., Roussel N., Zhu X., “Acyclic 4-choosability of planar graphs”, Discrete Math., 311:1 (2011), 92–101  crossref  mathscinet  zmath  isi  elib
    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  crossref  mathscinet  zmath  isi  elib
    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  crossref  mathscinet  zmath  isi  elib
    5. 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
    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  crossref  mathscinet  zmath  isi  elib
    7. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib
    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  crossref  mathscinet  zmath  isi  elib
  • Number of views:
    This page:214
    Full text:40
    References:25

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