Processing math: 100%
Diskretnyi Analiz i Issledovanie Operatsii
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretnyi Analiz i Issledovanie Operatsii, 2009, Volume 16, Issue 2, Pages 16–20 (Mi da565)  

This article is cited in 18 scientific papers (total in 18 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
References:
Abstract: A graph G is (2,1)-colorable if its vertices can be partitioned into subsets V1 and V2 such that in G[V1] any component contains at most two vertices while G[V2] is edgeless. We prove that every graph G with the maximum average degree 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 Gn with mad(Gn)=(18n2)/(7n1) that is not (2,1)-colorable. Bibl. 5.
Keywords: planar graph, girth, coloring, partition.
Received: 09.02.2008
English version:
Journal of Applied and Industrial Mathematics, 2010, Volume 4, Issue 1, Pages 21–23
DOI: https://doi.org/10.1134/S1990478910010047
Bibliographic databases:
UDC: 519.172.2
Language: Russian
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
\Bibitem{BorIva09}
\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
\mathnet{http://mi.mathnet.ru/da565}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2574306}
\zmath{https://zbmath.org/?q=an:1249.05110}
\transl
\jour J. Appl. Industr. Math.
\yr 2010
\vol 4
\issue 1
\pages 21--23
\crossref{https://doi.org/10.1134/S1990478910010047}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77949893758}
Linking options:
  • https://www.mathnet.ru/eng/da565
  • https://www.mathnet.ru/eng/da/v16/i2/p16
  • This publication is cited in the following 18 articles:
    1. 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
    2. 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
    3. 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
    4. Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23  zmath  isi
    5. 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
    6. 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
    7. 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
    8. 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
    9. 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
    10. 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
    11. 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
    12. Alexandr Kostochka, Matthew Yancey, Lecture Notes in Computer Science, 7913, Computer Science – Theory and Applications, 2013, 224  crossref
    13. 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
    14. 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
    15. 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
    16. 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
    17. 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
    18. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретный анализ и исследование операций
    Statistics & downloads:
    Abstract page:636
    Full-text PDF :119
    References:64
    First page:3
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025