Аннотация:
Граф G называется (2,1)-раскрашиваемым, если множество его вершин можно разбить на два подмножества V1 и V2 так, что в G[V1] любая компонента содержит не более двух вершин, а в G[V2] нет рёбер. Доказано, что любой граф G с максимальной средней степенью mad(G) меньшей 7/3 является (2,1)-раскрашиваемым. Отсюда следует, что каждый плоский граф с обхватом не менее 14 является (2,1)-раскрашиваемым. Построен плоский граф Gn c mad(Gn)=(18n−2)/(7n−1), не являющийся (2,1)-раскрашиваемым. Библиогр. 5.
Образец цитирования:
О. В. Бородин, А. О. Иванова, “Почти правильные 2-раскраски вершин разреженных графов”, Дискретн. анализ и исслед. опер., 16:2 (2009), 16–20; J. Appl. Industr. Math., 4:1 (2010), 21–23
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
А. Н. Глебов, Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 6 на два леса с длиной цепей не больше 4”, Дискретн. анализ и исслед. опер., 21:2 (2014), 33–51; 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
О. В. Бородин, А. В. Косточка, “Вершинные разбиения разреженных графов на независимое множество и подграф максимальной степени не более 1”, Сиб. матем. журн., 52:5 (2011), 1004–1010; 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