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 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
\Bibitem{Bor09}
\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
\mathnet{http://mi.mathnet.ru/da590}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2649138}
\zmath{https://zbmath.org/?q=an:1249.05108}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 4
\pages 490--495
\crossref{https://doi.org/10.1134/S1990478910040034}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-78650058674}


Linking options:
  • http://mi.mathnet.ru/eng/da590
  • http://mi.mathnet.ru/eng/da/v16/i6/p3

    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-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
    References:36
    First page:2

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