Том 27, номер 4, 2020 г., Стр. 104-130

УДК 519.17
Малышев Д. С.
Полная сложностная дихотомия для запрещённых подграфов с 7 рёбрами в задаче о хроматическом индексе

Аннотация:
Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная классификация сложности задачи о рёберной раскраске для всех множеств запретов, каждый из которых имеет не более чем 7 рёбер.
Ил. 3, библиогр. 36.

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

DOI: 10.33048/daio.2020.27.682

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

Статья поступила 22 января 2020 г.
После доработки — 1 июня 2020 г.
Принята к публикации 11 июня 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] Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. 1981. Vol. 10, No. 4. P. 718–720.

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

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

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

[6] Hoàng C. T., 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.

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

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

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

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

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

[12] Malyshev D. S. Polynomial-time approximation algorithms for the coloring problem in some cases // J. Comb. Optim. 2017. Vol. 33. P. 809–813.

[13] 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. 2020. Vol. 93, No. 4. P. 503–552.

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

[15] Dai Y., Foley A., Hoàng C. T. 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.

[16] Fraser D. J., Hamela A. M., Hoàng C. T., Holmes K., LaMantia T. P. Characterizations of (4$K_{1}, C_{4}, C_{5}$)-free graphs // Discrete Appl. Math. 2017. Vol. 231. P. 166–174.

[17] Golovach P., 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.

[18] Broersma H. J., Golovach P. A., Paulusma D., Song J. Updating the complexity status of coloring graphs without a fixed induced linear forest // Theor. Comput. Sci. 2012. Vol. 414, No. 1. P. 9–19.

[19] Golovach P. A., Paulusma D., Song J. 4-Coloring $H$-free graphs when $H$ is small // Discrete Appl. Math. 2013. Vol. 161, No. 1–2. P. 140–150.

[20] Bonomo F., Chudnovsky M., Maceli P., Schaudt O., Stein M., Zhong M. Three-coloring and list three-coloring of graphs without induced paths on seven vertices // Combinatorica. 2018. Vol. 38, No. 4. P. 779–801.

[21] Spirkl S., Chudnovsky M., Zhong M. Four-coloring $P_6$-free graphs // Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms (San Diego, USA, Jan. 6–9, 2019). Philadelphia, PA: SIAM, 2019. P. 1239–1256.

[22] Hoàng C. T., Kaminski M., Lozin V. V., Sawada J., Shu X. Deciding $k$-colorability of $P_5$-free graphs in polynomial time // Algorithmica. 2010. Vol. 57, No. 1. P. 74–81.

[23] Huang S. Improved complexity results on $k$-coloring $P_t$-free graphs // Eur. J. Comb. 2016. Vol. 51. P. 336–346.

[24] Malyshev D. S. The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs // Discrete Math. 2015. Vol. 338, No. 11. P. 1860–1865.

[25] Malyshev D. S. The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs // Graphs Comb. 2017. Vol. 33, No. 4. P. 1009–1022.

[26] Сироткин Д. В., Малышев Д. С. О сложности задачи вершинной 3-раскраски для наследственных классов графов, определённых запретами небольшого размера // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 4. С. 112–130.

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

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

[29] Malyshev D. S. Complexity classification of the edge coloring problem for a family of graph classes // Discrete Math. Appl. 2017. Vol. 27, No. 2. P. 97–101.

[30] Schrijver A. Combinatorial optimization – Polyhedra and efficiency. Heidelberg: Springer, 2003. 1882 p.

[31] König D. Gráfok és alkalmazásuk a determinánsok és a halmazok elméletére // Matematikai és Természettudományi Értesitö. 1916. Vol. 34. P. 104–119. [Hungarian].

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

[33] 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.; Vol. 2518).

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

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

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