General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Sib. Èlektron. Mat. Izv.:

Personal entry:
Save password
Forgotten password?

Sib. Èlektron. Mat. Izv., 2006, Volume 3, Pages 441–450 (Mi semr219)  

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

Research papers

Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth $6$

O. V. Borodina, A. O. Ivanovab, T. K. Neustroevab

a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b Yakutsk State University

Abstract: A trivial lower bound for the $2$-distance chromatic number $\chi_2(G)$ of any graph $G$ with maximum degree $\Delta$ is $\Delta+1$. It is known that if $G$ is planar and its girth is at least $7$, then for large enough $\Delta$ this bound is sharp, while for girth $6$ it is not true. We prove that if $G$ is planar, its girth is $6$, every edge is incident with a $2$-vertex, and $\Delta\ge31$, then $\chi_2(G)=\Delta+1$.

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

Bibliographic databases:

Document Type: Article
UDC: 519.172.2
MSC: 05С15
Received December 1, 2006, published December 29, 2006

Citation: O. V. Borodin, A. O. Ivanova, T. K. Neustroeva, “Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth $6$”, Sib. Èlektron. Mat. Izv., 3 (2006), 441–450

Citation in format AMSBIB
\by O.~V.~Borodin, A.~O.~Ivanova, T.~K.~Neustroeva
\paper Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth~$6$
\jour Sib. \`Elektron. Mat. Izv.
\yr 2006
\vol 3
\pages 441--450

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., Kostochka A.V., Sheikh N.N., “Minimax degrees of quasiplanar graphs with no short cycles other than triangles”, Taiwanese J. Math., 12:4 (2008), 873–886  mathscinet  zmath  isi  elib
    2. O. V. Borodin, A. O. Ivanova, “List 2-distance $(\Delta+2)$-coloring of planar graphs with girth 6 and $\Delta\ge24$”, Siberian Math. J., 50:6 (2009), 958–964  mathnet  crossref  mathscinet  isi
    3. Borodin O.V., Ivanova A.O., “$2$-distance $(\Delta+2)$-coloring of planar graphs with girth six and $\Delta\ge 18$”, Discrete Math., 309:23-24 (2009), 6496–6502  crossref  mathscinet  zmath  isi  elib
    4. Borodin O.V., Ivanova A.O., “List 2-distance $(\Delta+2)$-coloring of planar graphs with girth six”, European J. Combin., 30:5 (2009), 1257–1262  crossref  mathscinet  zmath  isi  elib
    5. A. O. Ivanova, “Predpisannaya 2-distantsionnaya $(\Delta+1)$-raskraska ploskikh grafov s obkhvatom ne menee 7”, Diskretn. analiz i issled. oper., 17:5 (2010), 22–36  mathnet  mathscinet  zmath
    6. Borodin O.V., Ivanova A.O., Montassier M., Ochem P., Raspaud A., “Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most $k$”, J. Graph Theory, 65:2 (2010), 83–93  crossref  mathscinet  zmath  isi  elib
    7. 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
    8. 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
    9. 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
    10. 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
    11. Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539  crossref  mathscinet  mathscinet  zmath  isi  elib
    12. 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
    13. 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
  • Number of views:
    This page:252
    Full text:37

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