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)=(18n−2)/(7n−1) that is not (2,1)-colorable. Bibl. 5.
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
This publication is cited in the following 18 articles:
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
Hendrey K., Wood D.R., “Defective and Clustered Choosability of Sparse Graphs”, Comb. Probab. Comput., 28:5 (2019), 791–810
Wood D.R., “Defective and Clustered Graph Colouring”, Electron. J. Comb., 2018, DS23
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
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
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
Dorbec P., Montassier M., Ochem P., “Vertex Partitions of Graphs Into Cographs and Stars”, J. Graph Theory, 75:1 (2014), 75–90
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
Borodin O.V., Kostochka A., Yancey M., “On 1-Improper 2-Coloring of Sparse Graphs”, Discrete Math., 313:22 (2013), 2638–2649
Alexandr Kostochka, Matthew Yancey, Lecture Notes in Computer Science, 7913, Computer Science – Theory and Applications, 2013, 224
Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,1)$-coloring of sparse graphs”, Discrete Math., 312:6 (2012), 1128–1135
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
Borodin O.V., Ivanova A.O., Montassier M., Raspaud A., “$(k,j)$-coloring of sparse graphs”, Discrete Appl. Math., 159:17 (2011), 1947–1953
Borodin O.V., Ivanova A.O., “List strong linear 2-arboricity of sparse graphs”, J. Graph Theory, 67:2 (2011), 83–90
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
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