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



Sibirsk. Mat. Zh.:
Year:
Volume:
Issue:
Page:
Find






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


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
\Bibitem{BorIva11}
\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
\mathnet{http://mi.mathnet.ru/smj2217}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2858640}
\transl
\jour Siberian Math. J.
\yr 2011
\vol 52
\issue 3
\pages 411--425
\crossref{https://doi.org/10.1134/S0037446611030049}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000298648800004}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79959726108}


Linking options:
  • http://mi.mathnet.ru/eng/smj2217
  • http://mi.mathnet.ru/eng/smj/v52/i3/p522

    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. 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
    References:45
    First page:11

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