Diskretnyi Analiz i Issledovanie Operatsii
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, Issue 2, Pages 16–20 (Mi da565)  

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

Near-proper vertex 2-colorings of sparse graphs

O. V. Borodina, A. O. Ivanovab

a S. L. Sobolev Institute of Mathematics, SB RAS, Novosibirsk, Russia
b Institute of Mathematics at Yakutsk State University, Yakutsk, Russia

Abstract: A graph $G$ is $(2,1)$-colorable if its vertices can be partitioned into subsets $V_1$ and $V_2$ such that in $G[V_1]$ any component contains at most two vertices while $G[V_2]$ is edgeless. We prove that every graph $G$ with the maximum average degree $\mathrm{mad}(G)$ smaller than 7/3 is $(2,1)$-colorable. It follows that every planar graph with girth at least 14 is $(2,1)$-colorable. We also construct a planar graph $G_n$ with $\mathrm{mad}(G_n)=(18n-2)/(7n-1)$ that is not $(2,1)$-colorable. Bibl. 5.

Keywords: planar graph, girth, coloring, partition.

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

English version:
Journal of Applied and Industrial Mathematics, 2010, 4:1, 21–23

Bibliographic databases:

UDC: 519.172.2
Received: 09.02.2008

Citation: O. V. Borodin, A. O. Ivanova, “Near-proper vertex 2-colorings of sparse graphs”, Diskretn. Anal. Issled. Oper., 16:2 (2009), 16–20; J. Appl. Industr. Math., 4:1 (2010), 21–23

Citation in format AMSBIB
\by O.~V.~Borodin, A.~O.~Ivanova
\paper Near-proper vertex 2-colorings of sparse graphs
\jour Diskretn. Anal. Issled. Oper.
\yr 2009
\vol 16
\issue 2
\pages 16--20
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 1
\pages 21--23

Linking options:
  • http://mi.mathnet.ru/eng/da565
  • http://mi.mathnet.ru/eng/da/v16/i2/p16

    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., 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  scopus
    2. Montassier M., Raspaud A., Zhu Xuding, “Decomposition of sparse graphs into two forests, one having bounded maximum degree”, Inform. Process. Lett., 110:20 (2010), 913–916  crossref  mathscinet  zmath  isi  elib  scopus
    3. O. V. Borodin, A. V. Kostochka, “Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most $1$”, Siberian Math. J., 52:5 (2011), 796–801  mathnet  crossref  mathscinet  isi
    4. Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,j)$-coloring of sparse graphs”, Discrete Appl. Math., 159:17 (2011), 1947–1953  crossref  mathscinet  zmath  isi  elib  scopus
    5. Borodin O.V., Ivanova A.O., “List strong linear 2-arboricity of sparse graphs”, J. Graph Theory, 67:2 (2011), 83–90  crossref  mathscinet  zmath  isi  elib  scopus
    6. Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,1)$-coloring of sparse graphs”, Discrete Math., 312:6 (2012), 1128–1135  crossref  mathscinet  zmath  isi  elib  scopus
    7. Esperet L., Montassier M., Ochem P., Pinlou A., “A Complexity Dichotomy for the Coloring of Sparse Graphs”, J. Graph Theory, 73:1 (2013), 85–102  crossref  mathscinet  zmath  isi  elib  scopus
    8. Borodin O.V., Kostochka A., Yancey M., “On 1-Improper 2-Coloring of Sparse Graphs”, Discrete Math., 313:22 (2013), 2638–2649  crossref  mathscinet  zmath  isi  elib  scopus
    9. A. N. Glebov, D. Zh. Zambalaeva, “A partition of a planar graph with girth 6 into two forests containing no path of length greater than 4”, J. Appl. Industr. Math., 8:3 (2014), 317–328  mathnet  crossref  mathscinet
    10. Dorbec P., Kaiser T., Montassier M., Raspaud A., “Limits of Near-Coloring of Sparse Graphs”, J. Graph Theory, 75:2 (2014), 191–202  crossref  mathscinet  zmath  isi  elib  scopus
    11. Borodin O.V., Kostochka A.V., “Defective 2-Colorings of Sparse Graphs”, J. Comb. Theory Ser. B, 104 (2014), 72–80  crossref  mathscinet  zmath  isi  elib  scopus
    12. Dorbec P., Montassier M., Ochem P., “Vertex Partitions of Graphs Into Cographs and Stars”, J. Graph Theory, 75:1 (2014), 75–90  crossref  mathscinet  zmath  isi  elib  scopus
    13. Choi H., Choi I., Jeong J., Suh G., “(1, K)-Coloring of Graphs With Girth At Least Five on a Surface”, J. Graph Theory, 84:4 (2017), 521–535  crossref  mathscinet  zmath  isi  scopus
    14. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23  zmath  isi
    15. Hendrey K., Wood D.R., “Defective and Clustered Choosability of Sparse Graphs”, Comb. Probab. Comput., 28:5 (2019), 791–810  crossref  mathscinet  zmath  isi  scopus
  • Дискретный анализ и исследование операций
    Number of views:
    This page:482
    Full text:97
    First page:3

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