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., 2010, Volume 17, Number 5, Pages 22–36 (Mi da622)  

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

List 2-distance $(\Delta+1)$-coloring of planar graphs with girth at least 7

A. O. Ivanova

Institute of Mathematics at Yakutsk State University, Yakutsk, Russia

Abstract: A trivial lower bound for the 2-distance chromatic number $\chi_2(G)$ of every graph $G$ with maximum degree $\Delta$ is $\Delta+1$. There are graphs with arbitrarily large $\Delta$ and girth $g\le6$ having $\chi_2(G)\ge\Delta+2$. In the paper are improved previously known restrictions on $\Delta$ and $g$ under which every planar graph $G$ has $\chi_2(G)=\Delta+1$. Ill. 2, bibliogr. 24.

Keywords: planar graph, 2-distance coloring, list coloring.

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

Bibliographic databases:
UDC: 519.17
Received: 02.02.2010
Revised: 28.07.2010

Citation: A. O. Ivanova, “List 2-distance $(\Delta+1)$-coloring of planar graphs with girth at least 7”, Diskretn. Anal. Issled. Oper., 17:5 (2010), 22–36

Citation in format AMSBIB
\Bibitem{Iva10}
\by A.~O.~Ivanova
\paper List 2-distance $(\Delta+1)$-coloring of planar graphs with girth at least~7
\jour Diskretn. Anal. Issled. Oper.
\yr 2010
\vol 17
\issue 5
\pages 22--36
\mathnet{http://mi.mathnet.ru/da622}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2779349}
\zmath{https://zbmath.org/?q=an:1249.05118}


Linking options:
  • http://mi.mathnet.ru/eng/da622
  • http://mi.mathnet.ru/eng/da/v17/i5/p22

    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, “Injective $(\Delta+1)$-coloring of planar graphs with girth 6”, Siberian Math. J., 52:1 (2011), 23–29  mathnet  crossref  mathscinet  isi
    2. O. V. Borodin, A. O. Ivanova, “2-distance 4-coloring of planar subcubic graphs”, J. Appl. Industr. Math., 5:4 (2011), 535–541  mathnet  crossref  mathscinet  zmath
    3. Borodin O.V., Ivanova A.O., “List injective colorings of planar graphs”, Discrete Math., 311:2–3 (2011), 154–165  crossref  mathscinet  zmath  isi  elib  scopus
    4. Ivanova A.O., “2-granevaya 4-raskrashivaemost ploskikh grafov s obkhvatom ne menee 22”, Matematicheskie zametki YaGU, 18:2 (2011), 52–63  zmath  elib
    5. 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  scopus
    6. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  zmath  isi  elib  scopus
    7. Zhu H. Hou L. Chen W. Lu X., “The l(P, Q)-Labelling of Planar Graphs Without 4-Cycles”, Discrete Appl. Math., 162 (2014), 355–363  crossref  mathscinet  zmath  isi  elib  scopus
    8. Bonamy M. Leveque B. Pinlou A., “Graphs with Maximum Degree Delta >= 17 and Maximum Average Degree Less Than 3 Are List 2-Distance (Delta+2)-Colorable”, Discrete Math., 317 (2014), 19–32  crossref  mathscinet  zmath  isi  elib  scopus
    9. Bonamy M. Leveque B. Pinlou A., “2-Distance Coloring of Sparse Graphs”, J. Graph Theory, 77:3 (2014), 190–218  crossref  mathscinet  zmath  isi  elib  scopus
    10. Zhu H., Chen Sh., Miao L., Lv X., “On List R-Hued Coloring of Planar Graphs”, J. Comb. Optim., 34:3 (2017), 874–890  crossref  mathscinet  zmath  isi  scopus
    11. Zhu H., Gu Yu., Sheng J., Lu X., “List 2-Distance -Coloring of Planar Graphs Without 4,5-Cycles”, J. Comb. Optim., 36:4 (2018), 1411–1424  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:361
    Full text:75
    References:36
    First page:5

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