Abstract:
A graph G is (1,0)-colorable if its vertex set can be partitioned into subsets V1 and V0 so that in G[V1] every vertex has degree at most 1, while G[V0] is edgeless. We prove that every graph with maximum average degree at most 125 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 125 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)⩾−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.
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
\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://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000298650500004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80155142461}
Linking options:
https://www.mathnet.ru/eng/smj2253
https://www.mathnet.ru/eng/smj/v52/i5/p1004
This publication is cited in the following 23 articles:
Cristina Bazgan, André Nichterlein, Sofia Vazquez Alferez, “Destroying Densest Subgraphs is Hard”, Journal of Computer and System Sciences, 2025, 103635
Alexandr Kostochka, Jingwei Xu, “Sparse critical graphs for defective DP-colorings”, Discrete Mathematics, 347:5 (2024), 113899
Min Chen, André Raspaud, Weifan Wang, Weiqiang Yu, “An (F3,F5)-partition of planar graphs with girth at least 5”, Discrete Mathematics, 346:2 (2023), 113216
Chen M., Raspaud A., Yu W., “An (F-1, F-4)-Partition of Graphs With Low Genus and Girth At Least 6”, J. Graph Theory, 99:2 (2022), 186–206
Yifan Jing, Alexandr Kostochka, Fuhong Ma, Jingwei Xu, “Defective DP-colorings of sparse simple graphs”, Discrete Mathematics, 345:1 (2022), 112637
Jing Y. Kostochka A. Ma F. Sittitrai P. Xu J., “Defective Dp-Colorings of Sparse Multigraphs”, Eur. J. Comb., 93 (2021), 103267
Cranston D.W., Yancey M.P., “Vertex Partitions Into An Independent Set and a Forest With Each Component Small”, SIAM Discret. Math., 35:3 (2021), 1769–1791
Kostochka A. Xu J., “On 2-Defective Dp-Colorings of Sparse Graphs”, Eur. J. Comb., 91 (2021), 103217
Hendrey K., Wood D.R., “Defective and Clustered Choosability of Sparse Graphs”, Comb. Probab. Comput., 28:5 (2019), 791–810
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
Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23
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
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
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
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
Choi I., Raspaud A., “Planar Graphs With Girth At Least 5 Are (3,5)-Colorable”, Discrete Math., 338:4 (2015), 661–667
Montassier M., Ochem P., “Near-Colorings: Non-Colorable Graphs and Np-Completeness”, Electron. J. Comb., 22:1 (2015), P1.57
Dorbec P., Kaiser T., Montassier M., Raspaud A., “Limits of Near-Coloring of Sparse Graphs”, J. Graph Theory, 75:2 (2014), 191–202
Borodin O.V., Kostochka A.V., “Defective 2-Colorings of Sparse Graphs”, J. Comb. Theory Ser. B, 104 (2014), 72–80
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