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 6, Pages 3–11 (Mi da590)  

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

Acyclic 4-coloring of plane graphs without cycles of length 4 and 6

O. V. Borodin

S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia

Abstract: Every planar graph is known to be acyclically 5-colorable (Borodin, 1976), which bound is precise. Some sufficient conditions are also obtained for a planar graph to be acyclically 4-colorable. In particular, the acyclic 4-colorability was proved for the following planar graphs: without 3- and 4-cycles (Borodin, Kostochka and Woodall, 1999), without 4-, 5- and 6-cycles, (Montassier, Raspaud and Wang, 2006), without 4-, 6- and 7-cycles, and without 4-, 6- and 8-cycles (Chen, Raspaud, and Wang, 2009).
In this paper it is proved that each planar graph without 4- and 6-cycles is acyclically 4-colorable. Bibl. 17.

Keywords: planar graph, acyclically coloring, acyclic choosability.

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

English version:
Journal of Applied and Industrial Mathematics, 2010, 4:4, 490–495

Bibliographic databases:

UDC: 519.172
Received: 13.05.2009
Revised: 17.06.2009

Citation: O. V. Borodin, “Acyclic 4-coloring of plane graphs without cycles of length 4 and 6”, Diskretn. Anal. Issled. Oper., 16:6 (2009), 3–11; J. Appl. Industr. Math., 4:4 (2010), 490–495

Citation in format AMSBIB
\by O.~V.~Borodin
\paper Acyclic 4-coloring of plane graphs without cycles of length~4 and~6
\jour Diskretn. Anal. Issled. Oper.
\yr 2009
\vol 16
\issue 6
\pages 3--11
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 4
\pages 490--495

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-colorability of planar graphs without 4- and 5-cycles”, J. Appl. Industr. Math., 5:1 (2011), 31–43  mathnet  crossref  mathscinet  zmath
    2. 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
    3. 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
    4. Chen Min, Raspaud A., “On acyclic 4-choosability of planar graphs without short cycles”, Discrete Math., 310:15–16 (2010), 2113–2118  crossref  mathscinet  zmath  isi  elib  scopus
    5. Chen Min, Raspaud A., Roussel N., Zhu Xuding, “Acyclic 4-choosability of planar graphs”, Discrete Math., 311:1 (2011), 92–101  crossref  mathscinet  zmath  isi  elib  scopus
    6. 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
    7. 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
    8. 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
    9. Chen M., Raspaud A., “A Sufficient Condition for Planar Graphs to Be Acyclically 5-Choosable”, J. Graph Theory, 70:2 (2012), 135–151  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. 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
    12. Zhu E., Li Z., Shao Z., Xu J., “On Acyclically 4-Colorable Maximal Planar Graphs”, Appl. Math. Comput., 329 (2018), 402–407  crossref  mathscinet  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:342
    Full text:64
    First page:2

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