Том 28, номер 1, 2021 г., Стр. 15-47

УДК 519.17
Развенская О. О., Малышев Д. С.
Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторых двух наследственных классов графов

Аннотация:
Задача о взвешенной вершинной раскраске для заданного взвешенного графа состоит в том, чтобы минимизировать количество используемых цветов так, что для каждой вершины количество назначаемых ей цветов равно её весу и назначаемые множества цветов для любых смежных вершин не пересекаются. Для всех наследственных классов, определяемых двумя связными 5-вершинными порождёнными запретами, кроме четырёх случаев, известна вычислительная сложность варианта задачи о взвешенной вершинной раскраске с единичными весами. Для четырёх из шести попарных пересечений данных четырёх классов ранее была доказана разрешимость задачи о взвешенной вершинной раскраске за полиномиальное от суммы весов вершин время. Для оставшихся двух таких пересечений данный факт устанавливается в настоящей работе.
Библиогр. 17.

Ключевые слова: задача о взвешенной вершинной раскраске, наследственный класс, вычислительная сложность.

DOI: 10.33048/daio.2021.28.685

Развенская Ольга Олеговна ¹
Малышев Дмитрий Сергеевич ¹
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
е-mail: olga-olegov@yandex.ru, dsmalyshev@rambler.ru

Статья поступила 29 апреля 2020 г.
После доработки — 3 ноября 2020 г.
Принята к публикации 5 ноября 2020 г.

Литература

[1] Garey M. R., Johnson D. S. Computers and intractability: A guide to the theory of NP-completeness. New York: Freeman, 1979. 338 p.

[2] Král’ D., Kratochvíl J., Tuza Z., Woeginger G. Complexity of coloring graphs without forbidden induced subgraphs // Graph-Theoretic Concepts in Computer Science. Proc. 27th Int. Workshop (Boltenhagen, Germany, June 14–16, 2001). Heidelberg: Springer, 2001. P. 254–262. (Lect. Notes Comput. Sci.; Vol. 2204).

[3] Lozin V. V., Malyshev D. S. Vertex coloring of graphs with few obstructions // Discrete Appl. Math. 2017. Vol. 216. P. 273–280.

[4] Golovach P. A., Johnson M., Paulusma D., Song J. A survey on the computational complexity of coloring graphs with forbidden subgraphs // J. Graph Theory. 2017. Vol. 84. P. 331–363.

[5] Cameron K., Huang S., Penev I., Sivaraman V. The class of ($P_7, C_4, C_5$)- free graphs: decomposition, algorithms, and $\chi$-boundedness // J. Graph Theory. 2019. Vol. 93, No. 4. P. 503–552.

[6] Cameron K., da Silva M., Huang S., Vuskovic K. Structure and algorithms for (cap, even hole)-free graphs // Discrete Math. 2018. Vol. 341. P. 463–473.

[7] Dai Y., Foley A., Hoàng C. On coloring a class of claw-free graphs: to the memory of Frédéric Maffray // Electron. Notes Theor. Comput. Sci. 2019. Vol. 346. P. 369–377.

[8] Fraser D., Hamela A., Hoàng C., Holmes K., LaMantia T. Characterizations of ($4K_1, C_4, C_5$)-free graphs // Discrete Appl. Math. 2017. Vol. 231. P. 166–174.

[9] Hoàng C., Lazzarato D. Polynomial-time algorithms for minimum weighted colorings of ($P_5, \overline{P}_5$)-free graphs and similar graph classes // Discrete Appl. Math. 2015. Vol. 186. P. 105–111.

[10] Karthick T., Maffray F., Pastor L. Polynomial cases for the vertex coloring problem // Algorithmica. 2017. Vol. 81, No. 3. P. 1053–1074.

[11] Malyshev D. S. The coloring problem for classes with two small obstructions // Optim. Lett. 2014. Vol. 8, No. 8. P. 2261–2270.

[12] Malyshev D. S. Two cases of polynomial-time solvability for the coloring problem // J. Comb. Optim. 2016. Vol. 31, No. 2. P. 833–845.

[13] Malyshev D. S. The weighted coloring problem for two graph classes characterized by small forbidden induced structures // Discrete Appl. Math. 2018. Vol. 47. P. 423–432.

[14] Malyshev D. S., Lobanova O. O. Two complexity results for the vertex coloring problem // Discrete Appl. Math. 2017. Vol. 219. P. 158–166.

[15] Грибанов Д. В., Малышев Д. C., Мокеев Д. Б. Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторого наследственного класса с 5-вершинными запретами // Дискрет. анализ и исслед. опер. 2020. Т. 27, № 3. C. 71–87.

[16] Chudnovsky M., Robertson N., Seymour P., Thomas R. The strong perfect graph theorem // Ann. Math. 2006. Vol. 164. P. 51–229.

[17] Grötschel M., Lovász L., Schrijver A. Polynomial algorithms for perfect graphs // Ann. Discrete Math. 1984. Vol. 21. P. 325–356.