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

 Sibirsk. Mat. Zh.: Year: Volume: Issue: Page: Find

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

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

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
\Bibitem{BorKos11} \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 \mathnet{http://mi.mathnet.ru/smj2253} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2908122} \transl \jour Siberian Math. J. \yr 2011 \vol 52 \issue 5 \pages 796--801 \crossref{https://doi.org/10.1134/S0037446611050041} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000298650500004} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80155142461} 

• http://mi.mathnet.ru/eng/smj2253
• http://mi.mathnet.ru/eng/smj/v52/i5/p1004

 SHARE:

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
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
3. Borodin O.V., Kostochka A., Yancey M., “On 1-Improper 2-Coloring of Sparse Graphs”, Discrete Math., 313:22 (2013), 2638–2649
4. Dorbec P., Kaiser T., Montassier M., Raspaud A., “Limits of Near-Coloring of Sparse Graphs”, J. Graph Theory, 75:2 (2014), 191–202
5. Borodin O.V., Kostochka A.V., “Defective 2-Colorings of Sparse Graphs”, J. Comb. Theory Ser. B, 104 (2014), 72–80
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
7. Choi I., Raspaud A., “Planar Graphs With Girth At Least 5 Are (3,5)-Colorable”, Discrete Math., 338:4 (2015), 661–667
8. Montassier M., Ochem P., “Near-Colorings: Non-Colorable Graphs and Np-Completeness”, Electron. J. Comb., 22:1 (2015), P1.57
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
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
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
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
13. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23
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
•  Number of views: This page: 228 Full text: 56 References: 38 First page: 1