Том 29, номер 2, 2022 г., Стр. 38-61

УДК 519.17
Малышев Д. С., Дугинов О. И.
О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами

Аннотация:
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы смежные рёбра были окрашены в разные цвета. Для всех классов графов, определяемых множествами запрещённых подграфов с 7 рёбрами каждый, известен сложностной статус данной задачи. В настоящей работе рассматривается случай запретов с 8 рёбрами. Нетрудно заметить, что задача о рёберной раскраске будет NP-трудной для такого класса, если среди его 8-рёберных запретов нет субкубического леса. В данной работе доказывается, что запрещение любого субкубического 8-рёберного леса порождает класс с полиномиальной разрешимостью задачи о рёберной раскраске, кроме случаев, образованных дизъюнктной суммой одного из четырёх лесов и пустого графа. Для всех оставшихся случаев доказывается аналогичный результат для пересечения с множеством графов максимальной степени не менее чем 4.
Ил. 2, библиогр. 14

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

DOI: 10.33048/daio.2022.29.721

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

Статья поступила 7 июля 2021 г.
После доработки — 4 февраля 2022 г.
Принята к публикации 7 февраля 2022 г.

Литература

[1] Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. 1981. V. 10, No. 4. P. 718–720.

[2] Визинг В. Г. Об оценке хроматического класса $p$-графа // Дискретный анализ. Вып. 3. Новосибирск: Ин-т математики, 1964. С. 25–30.

[3] Galby E., Lima P. T., Paulusma D., Ries B. Classifying $k$-edge colouring for $H$-free graphs // Inf. Process. Lett. 2019. V. 146. P. 39–43.

[4] Malyshev D. S. The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices // Сиб. электрон. мат. изв. 2014. Т. 11. С. 811–822.

[5] Малышев Д. С. Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов // Дискрет. математика. 2016. Т. 28, вып. 2. С. 44–50.

[6] Малышев Д. С. Полная сложностная дихотомия для запрещённых подграфов с 7 рёбрами в задаче о хроматическом индексе // Дискрет. анализ и исслед. операций. 2020. Т. 27, № 4. С. 104–130.

[7] Kaminski M., Lozin V. V. Coloring edges and vertices of graphs without short or long cycles // Contrib. Discrete Math. 2007. V. 2, No. 1. P. 61–66.

[8] Schrijver A. Combinatorial optimization. Polyhedra and efficiency. Heidelberg: Springer, 2003. 1879 p.

[9] Courcelle B., Makowsky J. A., Rotics U. Linear time solvable optimization problems on graphs of bounded clique-width // Theory Comput. Syst. 2000. V. 33, No. 2. P. 125–150.

[10] Gurski F., Wanke E. Line graphs of bounded clique-width // Discrete Math. 2007. V. 307, No. 22. P. 2734–2754.

[11] Kobler D., Rotics U. Edge dominating set and colorings on graphs with fixed clique-width // Discrete Appl. Math. 2003. V. 126, No. 2–3. P. 197–223.

[12] Boliac R., Lozin V. V. On the clique-width of graphs in hereditary classes // Algorithms and Computation. Proc. 13th Int. Symp. (Vancouver, Canada, Nov. 21–23, 2002). Heidelberg: Springer, 2002. P. 44–54. (Lect. Notes Comput. Sci.; V. 2518).

[13] Corneil D. G., Rotics U. On the relationship between clique-width and treewidth // SIAM J. Comput. 2005. V. 34, No. 4. P. 825–847.

[14] Gurski F., Wanke E. The tree-width of clique-width bounded graphs without $K_{n, n}$ // Graph-Theoretic Concepts in Computer Science. Proc. 26th Int. Workshop (Konstanz, Germany, June 15–17, 2000). Heidelberg: Springer, 2000. P. 196–205. (Lect. Notes Comput. Sci.; V. 1928).