Loading [MathJax]/jax/output/CommonHTML/jax.js
Sibirskii Matematicheskii Zhurnal
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sibirskii Matematicheskii Zhurnal, 2011, Volume 52, Number 5, Pages 1004–1010 (Mi smj2253)  

This article is cited in 23 scientific papers (total in 23 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
References:
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.
Keywords: planar graphs, coloring, girth.
Received: 15.07.2010
English version:
Siberian Mathematical Journal, 2011, Volume 52, Issue 5, Pages 796–801
DOI: https://doi.org/10.1134/S0037446611050041
Bibliographic databases:
Document Type: Article
UDC: 519.17
Language: Russian
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://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:
    1. Cristina Bazgan, André Nichterlein, Sofia Vazquez Alferez, “Destroying Densest Subgraphs is Hard”, Journal of Computer and System Sciences, 2025, 103635  crossref
    2. Alexandr Kostochka, Jingwei Xu, “Sparse critical graphs for defective DP-colorings”, Discrete Mathematics, 347:5 (2024), 113899  crossref
    3. 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  crossref
    4. 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  crossref  mathscinet  isi  scopus
    5. Yifan Jing, Alexandr Kostochka, Fuhong Ma, Jingwei Xu, “Defective DP-colorings of sparse simple graphs”, Discrete Mathematics, 345:1 (2022), 112637  crossref
    6. Jing Y. Kostochka A. Ma F. Sittitrai P. Xu J., “Defective Dp-Colorings of Sparse Multigraphs”, Eur. J. Comb., 93 (2021), 103267  crossref  mathscinet  zmath  isi  scopus
    7. 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  crossref  mathscinet  zmath  isi  scopus
    8. Kostochka A. Xu J., “On 2-Defective Dp-Colorings of Sparse Graphs”, Eur. J. Comb., 91 (2021), 103217  crossref  mathscinet  zmath  isi  scopus
    9. 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
    10. 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
    11. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23  zmath  isi
    12. 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
    13. 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
    14. 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
    15. 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
    16. 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
    17. Montassier M., Ochem P., “Near-Colorings: Non-Colorable Graphs and Np-Completeness”, Electron. J. Comb., 22:1 (2015), P1.57  mathscinet  zmath  isi  elib
    18. 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
    19. 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
    20. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Сибирский математический журнал Siberian Mathematical Journal
    Statistics & downloads:
    Abstract page:409
    Full-text PDF :106
    References:84
    First page:1
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025