General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Sibirsk. Mat. Zh.:

Personal entry:
Save password
Forgotten password?

Sibirsk. Mat. Zh., 2011, Volume 52, Number 5, Pages 1004–1010 (Mi smj2253)  

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

Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most $1$

O. V. Borodinab, A. V. Kostochkaac

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c University of Illinois, Urbana, USA

Abstract: A graph $G$ is $(1,0)$-colorable if its vertex set can be partitioned into subsets $V_1$ and $V_0$ so that in $G[V_1]$ every vertex has degree at most $1$, while $G[V_0]$ is edgeless. We prove that every graph with maximum average degree at most $\frac{12}5$ is $(1,0)$0)-colorable. In particular, every planar graph with girth at least $12$ is $(1,0)$-colorable. On the other hand, we construct graphs with the maximum average degree arbitrarily close (from above) to $\frac{12}5$ which are not $(1,0)$-colorable.
In fact, we prove a stronger result by establishing the best possible sufficient condition for the $(1,0)$-colorability of a graph $G$ in terms of the minimum, $Ms(G)$, of $6|V(A)|-5|E(A)|$ over all subgraphs $A$ of $G$. Namely, every graph $G$ with $Ms(G)\ge-2$ is proved to be $(1,0)$-colorable, and we construct an infinite series of non-$(1,0)$-colorable graphs $G$ with $Ms(G)=-3$.

Keywords: planar graphs, coloring, girth.

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

English version:
Siberian Mathematical Journal, 2011, 52:5, 796–801

Bibliographic databases:

UDC: 519.17
Received: 15.07.2010

Citation: 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$”, Sibirsk. Mat. Zh., 52:5 (2011), 1004–1010; Siberian Math. J., 52:5 (2011), 796–801

Citation in format AMSBIB
\by O.~V.~Borodin, A.~V.~Kostochka
\paper Vertex decompositions of sparse graphs into an independent vertex set and a~subgraph of maximum degree at most~$1$
\jour Sibirsk. Mat. Zh.
\yr 2011
\vol 52
\issue 5
\pages 1004--1010
\jour Siberian Math. J.
\yr 2011
\vol 52
\issue 5
\pages 796--801

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., Montassier M., Raspaud A., “(k, 1)-coloring of sparse graphs”, Discrete Math, 312:6 (2012), 1128–1135  crossref  mathscinet  zmath  isi  elib  scopus
    2. 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
    3. 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
    4. 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
    5. 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
    6. Kim J., Kostochka A., Zhu X., “Improper Coloring of Sparse Graphs With a Given Girth, i: (0,1)-Colorings of Triangle-Free Graphs”, Eur. J. Comb., 42 (2014), 26–48  crossref  mathscinet  zmath  isi  elib  scopus
    7. Choi I., Raspaud A., “Planar Graphs With Girth At Least 5 Are (3,5)-Colorable”, Discrete Math., 338:4 (2015), 661–667  crossref  mathscinet  zmath  isi  elib  scopus
    8. Montassier M., Ochem P., “Near-Colorings: Non-Colorable Graphs and Np-Completeness”, Electron. J. Comb., 22:1 (2015), P1.57  mathscinet  zmath  isi  elib
    9. J. Kim, A. Kostochka, X. Zhu, “Improper coloring of sparse graphs with a given girth, II: constructions”, J. Graph Theory, 81:4 (2016), 403–413  crossref  mathscinet  zmath  isi  elib  scopus
    10. H. Choi, I. Choi, J. Jeong, G. Suh, “(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
    11. M. Zhang, M. Chen, Y. Wang, “A sufficient condition for planar graphs with girth 5 to be (1,7)-colorable”, J. Comb. Optim., 33:3 (2017), 847–865  crossref  mathscinet  zmath  isi  scopus
    12. Chen M., Yu W., Wang W., “On the Vertex Partitions of Sparse Graphs Into An Independent Vertex Set and a Forest With Bounded Maximum Degree”, Appl. Math. Comput., 326 (2018), 117–123  crossref  mathscinet  zmath  isi  scopus
    13. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23  zmath  isi
    14. Dross F., Montassier M., Pinlou A., “Partitioning Sparse Graphs Into An Independent Set and a Forest of Bounded Degree”, Electron. J. Comb., 25:1 (2018), P1.45  mathscinet  zmath  isi
  • Сибирский математический журнал Siberian Mathematical Journal
    Number of views:
    This page:228
    Full text:56
    First page:1

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