Том 27, номер 3, 2020 г., Стр. 53-70

УДК 519.17
Грибанов Д. В., Малышев Д. С., Мокеев Д. Б.
Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторого наследственного класса графов с 5-вершинными запретами

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

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

DOI: 10.33048/daio.2020.27.668

Грибанов Дмитрий Владимирович ^1,2
Малышев Дмитрий Сергеевич ^1,2
Мокеев Дмитрий Борисович ^2,1
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
е-mail: dimitry.gribanov@gmail.com, dsmalyshev@rambler.ru, mokeevdb@gmail.com

Статья поступила 25 июля 2019 г.
После доработки — 6 января 2020 г.
Принята к публикации 19 февраля 2020 г.

Литература

[1] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[2] Král’ D., Kratochvíl J., Tuza Z., Woeginger G. Complexity of coloring graphs without forbidden induced subgraphs // Proc. 27th Int. Workshop on Graph-Theoretic Concepts in Computer Science (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] Malyshev D. S. Polynomial-time approximation algorithms for the coloring problem in some cases // J. Comb. Optim. 2017. Vol. 33, No 3. P. 809–813.

[5] Dabrowski K., Golovach P. A., Paulusma D. Colouring of graphs with Ramsey-type forbidden subgraphs // Theor. Comput. Sci. 2014. Vol. 522. P. 34–43.

[6] Dabrowski K., Lozin V. V., Raman R., Ries B. Colouring vertices of triangle-free graphs without forests // Discrete Math. 2012. Vol. 312, No 7. P. 1372–1385.

[7] 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.

[8] Golovach P. A., Paulusma D., Ries B. Coloring graphs characterized by a forbidden subgraph // Discrete Appl. Math. 2015. Vol. 180. P. 101–110.

[9] Hoàng C., Lazzarato D. Polynomial-time algorithms for minimum weighted colorings of ($P_5$, $\bar{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. 2015. 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] Cournier A., Habib M. A new linear algorithm for modular decomposition // Trees in Algebra and Programming – CAAP’94 (Proc. 19th Int. Colloq., Edinburgh, UK, Apr. 11–13, 1994), Heidelberg: Springer, 1994. P. 68–84. (Lect. Notes Comput. Sci.; Vol. 787).

[16] Tarjan R. E. Decomposition by clique separators // Discrete Math. 1985. Vol. 55, No 2. P. 221–232.

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

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