General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Sibirsk. Mat. Zh.:

Personal entry:
Save password
Forgotten password?

Sibirsk. Mat. Zh., 2011, Volume 52, Number 3, Pages 522–541 (Mi smj2217)  

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

Acyclic 5-choosability of planar graphs without 4-cycles

O. V. Borodinab, A. O. Ivanovac

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University, Novosibirsk
c Institute for Mathematics and Informatics, Yakutsk State University, Yakutsk

Abstract: The conjecture on the acyclic 5-choosability of planar graphs (Borodin et al., 2002) as yet has been verified only for several restricted classes of graphs: those of girth at least 5 (Montassier, Ochem, and Raspaud, 2006), without 4- and 5-cycles or without 4- and 6-cycles (Montassier, Raspaud, and Wang, 2007), with neither 4-cycles nor chordal 6-cycles (Zhang and Xu, 2009), with neither 4- cycles nor two 3-cycles at distance less than 3 (Chen and Wang, 2008), and with neither 4-cycles nor intersecting 3-cycles (Chen and Raspaud, 2010). Wang and Chen (2009) proved that the planar graphs without 4-cycles are acyclically 6-choosable. We prove that a planar graph without 4-cycles is acyclically 5-choosable, which is a common strengthening of all above-mentioned results.

Keywords: graph, planar graph, coloring, acyclic coloring, list coloring.

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

English version:
Siberian Mathematical Journal, 2011, 52:3, 411–425

Bibliographic databases:

UDC: 519.17
Received: 18.07.2010

Citation: O. V. Borodin, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Sibirsk. Mat. Zh., 52:3 (2011), 522–541; Siberian Math. J., 52:3 (2011), 411–425

Citation in format AMSBIB
\by O.~V.~Borodin, A.~O.~Ivanova
\paper Acyclic 5-choosability of planar graphs without 4-cycles
\jour Sibirsk. Mat. Zh.
\yr 2011
\vol 52
\issue 3
\pages 522--541
\jour Siberian Math. J.
\yr 2011
\vol 52
\issue 3
\pages 411--425

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. 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
    2. 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
    3. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib  scopus
    4. 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
    5. Wang WeiFan, Zhang Ge, Chen Min, “Acyclic 6-Choosability of Planar Graphs Without Adjacent Short Cycles”, Sci. China-Math., 57:1 (2014), 197–209  crossref  mathscinet  zmath  isi  elib  scopus
    6. Cranston D.W., West D.B., “An Introduction to the Discharging Method Via Graph Coloring”, Discrete Math., 340:4 (2017), 766–793  crossref  mathscinet  zmath  isi  scopus
    7. Sun Y., Chen M., Chen D., “Acyclic 4-Choosability of Planar Graphs Without Intersecting Short Cycles”, Discret. Math. Algorithms Appl., 10:1 (2018), 1850014  crossref  mathscinet  zmath  isi  scopus
    8. Sun L., “A Sufficient Condition For Acyclic 5-Choosability of Planar Graphs Without 5-Cycles”, Bull. Korean. Math. Soc., 55:2 (2018), 415–430  crossref  mathscinet  zmath  isi  scopus
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:228
    Full text:52
    First page:11

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