Полная сложностная дихотомия задачи о рёберной раскраске для всех множеств 8-рёберных запрещённых подграфов

Полная сложностная дихотомия задачи о рёберной раскраске для всех множеств 8-рёберных запрещённых подграфов

Малышев Д. С., Дугинов О. И.
Дискретный анализ и исследование операций, 30, 4, 91-109 (2023)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2023.30.758

Аннотация:

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

Литература:
  1. Holyer I. The NP-completeness of edge-coloring // SIAM J. Computing. 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. Малышев Д. С., Дугинов О. И. О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами // Дискрет. анализ и исслед. операций. 2022. Т. 29, № 2. С. 38–61.
     
  8. Barnaby M., Paulusma D., Siani S. Colouring graphs of bounded diameter in the absence of small cycles // Discrete Appl. Math. 2022. V. 314, No. 15. P. 150–161.
     
  9. 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. V. 38, No. 4. P. 779–801.
     
  10. 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. V. 414, No. 1. P. 9–19.
     
  11. 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. V. 93, No. 4. P. 503–552.
     
  12. Cameron K., da Silva M., Huang S., Vuskovic K. Structure and algorithms for (cap, even hole)-free graphs // Discrete Math. 2018. V. 341. P. 463–473.
     
  13. 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. V. 346. P. 369–377.
     
  14. 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. V. 231. P. 166–174.
     
  15. Golovach P., Johnson M., Paulusma D., Song J. A survey on the computational complexity of coloring graphs with forbidden subgraphs // J. Graph Theory. 2017. V. 84. P. 331–363.
     
  16. Golovach P. A., Paulusma D., Song J. 4-Coloring $H$-free graphs when $H$ is small // Discrete Appl. Math. 2013. V. 161, No. 1–2. P. 140–150.
     
  17. Hoàng C., Kamiński M., Lozin V. V., Sawada J., Shu X. Deciding $k$-colorability of $P_5$-free graphs in polynomial time // Algorithmica. 2010. V. 57, No. 1. P. 74–81.
     
  18. 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. V. 186. P. 105–111.
     
  19. Huang S. Improved complexity results on $k$-coloring $P_t$-free graphs // Eur. J. Comb. 2016. V. 51. P. 336–346.
     
  20. Karthick T., Maffray F., Pastor L. Polynomial cases for the vertex coloring problem // Algorithmica. 2017. V. 81, No. 3. P. 1053–1074.
     
  21. Klimošová T., Malík J., Masařík T., Novotná J., Paulusma D., Slívová V. Colouring ($P_r + P_s$)-free graphs // Algorithmica. 2020. V. 82, No. 7. P. 1833–1858.
     
  22. Král’ D., Kratochvíl J., Tuza Z., Woeginger G. Complexity of coloring graphs without forbidden induced subgraphs // Proc. 27th Int. Workshop Graph-Theoretic Concepts in Computer Science (Boltenhagen, Germany, June 14–16, 2001). Heidelberg: Springer, 2001. P. 254–262. (Lect. Notes Comput. Sci.; V. 2204).
     
  23. Lozin V. V., Malyshev D. S. Vertex coloring of graphs with few obstructions // Discrete Appl. Math. 2017. V. 216. P. 273–280.
     
  24. Malyshev D. S. The coloring problem for classes with two small obstructions // Optim. Lett. 2014. V. 8, No. 8. P. 2261–2270.
     
  25. Malyshev D. S. The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs // Discrete Math. 2015. V. 338, No. 11. P. 1860–1865.
     
  26. Malyshev D. S. Two cases of polynomial-time solvability for the coloring problem // J. Comb. Optim. 2016. V. 31, No. 2. P. 833–845.
     
  27. 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. V. 33, No. 4. P. 1009–1022.
     
  28. Malyshev D. S. Polynomial-time approximation algorithms for the coloring problem in some cases // J. Comb. Optim. 2017. V. 33. P. 809–813.
     
  29. Malyshev D. S. The weighted coloring problem for two graph classes characterized by small forbidden induced structures // Discrete Appl. Math. 2018. V. 47. P. 423–432.
     
  30. Malyshev D. S. The vertex colourability problem for {claw, butterfly}-free graphs is polynomial-time solvable // Optim. Lett. 2021. V. 15, No. 2. P. 311–326.
     
  31. Malyshev D. S., Lobanova O. O. Two complexity results for the vertex coloring problem // Discrete Appl. Math. 2017. V. 219. P. 158–166.
     
  32. Malyshev D. S., Pristavchenko O. V. An intractability result for the vertex 3-colourability problem // Optim. Lett. 2022. V. 16. P. 1403–1409.
     
  33. Malyshev D. S., Razvenskaya O. O., Pardalos P. M. The computational complexity of weighted vertex coloring for {$P_5, K_{2,3}, K^+_{2,3}$ }-free graphs // Optim. Lett. 2021. V. 15, No. 1. P. 137–152.
     
  34. Развенская О. О., Малышев Д. С. Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторых двух наследственных классов графов // Дискрет. анализ и исслед. операций. 2021. Т. 28, № 1. С. 15–47.
     
  35. Сироткин Д. В., Малышев Д. С. О сложности задачи вершинной 3-раскраски для наследственных классов графов, определённых запретами небольшого размера // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 4. С. 112–130.
     
  36. Spirkl S., Chudnovsky M., Zhong M. Four-coloring $P_6$-free graphs // Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms (San Diego, CA, USA, Jan. 6–9, 2019). Philadelphia, PA: SIAM, 2019. P. 1239–1256.
     
  37. Schrijver A. Combinatorial optimization: Polyhedra and efficiency. Heidelberg: Springer, 2003. 1882 p. (Algorithms Comb.; V. 24).
     
  38. Kamiński 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.

Разделы 2 и 3 выполнены при финансовой поддержке Российского фонда фундаментальных исследований и Белорусского республиканского фонда фундаментальных исследований (проект № 20–51–04001 (Ф21РМ-001)). Разделы 4 и 5 выполнены при финансовой поддержке Российского научного фонда (проект № 21–11–00194).

Малышев Дмитрий Сергеевич
  1. Национальный исследовательский университет «Высшая школа экономики», 
    ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
  2. Нижегородский гос. университет им. Н. И. Лобачевского, 
    пр. Гагарина, 23, 603950 Нижний Новгород, Россия

E-mail: dsmalyshev@rambler.ru

Дугинов Олег Иванович
  1. Белорусский гос. университет, 
    пр. Независимости, 4, 220030 Минск, Беларусь

E-mail: oduginov@gmail.com

Статья поступила 24 ноября 2022 г. 
После доработки — 10 июня 2023 г. 
Принята к публикации 22 июня 2023 г.

Abstract:

For a given graph, the edge-coloring problem is to minimize the number of colors sufficient to color all the graph edges so that any adjacent edges receive different colors. For all classes defined by sets of forbidden subgraphs, each with 7 edges, the complexity status of this problem is known. In this paper, we obtain a similar result for all sets of 8-edge prohibitions. 
Illustr. 2, bibliogr. 38.

References:
  1. I. Holyer, The NP-completeness of edge-coloring, SIAM J. Computing 10 (4), 718–720 (1981).
     
  2. V. G. Vizing, On an estimate of the chromatic index of a $p$-graph, Discrete Analysis, Vol. 3 (Inst. Mat. SO AN SSSR, Novosibirsk, 1964), pp. 25–30 [Russian].
     
  3. E. Galby, P. T. Lima, D. Paulusma, and B. Ries, Classifying $k$-edge colouring for $H$-free graphs, Inf. Process. Lett. 146, 39–43 (2019).
     
  4. D. S. Malyshev, The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices, Sib. Elektron. Mat. Izv. 11, 811–822 (2014).
     
  5. D. S. Malyshev, Complexity classification of the edge coloring problem for a family of graph classes, Diskretn. Mat. 28 (2), 44–50 (2016) [Russian] [Discrete Math. Appl. 27 (2), 97–101 (2017)].
     
  6. D. S. Malyshev, Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem, Diskretn. Anal. Issled. Oper. 27 (4), 104–130 (2020) [Russian] [J. Appl. Ind. Math. 14 (4), 706–721 (2020)].
     
  7. D. S. Malyshev and O. I. Duginov, Some cases of polynomial solvability for the edge colorability problem generated by forbidden 8-edge subcubic forests, Diskretn. Anal. Issled. Oper. 29 (2), 38–61 (2022) [Russian] [J. Appl. Ind. Math. 16 (2), 276–291 (2022)].
     
  8. M. Barnaby, D. Paulusma, and S. Siani, Colouring graphs of bounded diameter in the absence of small cycles, Discrete Appl. Math. 314 (15), 150–161 (2022).
     
  9. F. Bonomo, M. Chudnovsky, P. Maceli, O. Schaudt, M. Stein, and M. Zhong, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Combinatorica 38 (4), 779–801 (2018).
     
  10. H. J. Broersma, P. A. Golovach, D. Paulusma, and J. Song, Updating the complexity status of coloring graphs without a fixed induced linear forest, Theor. Comput. Sci. 414 (1), 9–19 (2012).
     
  11. K. Cameron, S. Huang, I. Penev, and V. Sivaraman, The class of ($P_7, C_4, C_5$)-free graphs: Decomposition, algorithms, and $\chi$-boundedness, J. Graph Theory 93 (4), 503–552 (2019).
     
  12. K. Cameron, M. da Silva, S. Huang, and K. Vuskovic, Structure and algorithms for (cap, even hole)-free graphs, Discrete Math. 341, 463–473 (2018).
     
  13. Y. Dai, A. Foley, and C. Hoàng, On coloring a class of claw-free graphs: To the memory of Frédéric Maffray, Electron. Notes Theor. Comput. Sci. 346, 369–377 (2019).
     
  14. D. Fraser, A. Hamela, C. Hoàng, K. Holmes, and T. LaMantia, Characterizations of ($4K_1, C_4, C_5$)-free graphs, Discrete Appl. Math. 231, 166–174 (2017).
     
  15. P. Golovach, M. Johnson, D. Paulusma, and J. Song, A survey on the computational complexity of coloring graphs with forbidden subgraphs, J. Graph Theory 84, 331–363 (2017).
     
  16. P. A. Golovach, D. Paulusma, and J. Song, 4-Coloring $H$-free graphs when $H$ is small, Discrete Appl. Math. 161 (1–2), 140–150 (2013).
     
  17. C. Hoàng, M. Kamiński, V. V. Lozin, J. Sawada, and X. Shu, Deciding $k$-colorability of $P_5$-free graphs in polynomial time, Algorithmica 57 (1), 74–81 (2010).
     
  18. C. Hoàng and D. Lazzarato, Polynomial-time algorithms for minimum weighted colorings of ($P_5, \bar{P}_5$)-free graphs and similar graph classes, Discrete Appl. Math. 186, 105–111 (2015).
     
  19. S. Huang, Improved complexity results on $k$-coloring $P_t$-free graphs, Eur. J. Comb. 51, 336–346 (2016).
     
  20. T. Karthick, F. Maffray, and L. Pastor, Polynomial cases for the vertex coloring problem, Algorithmica 81 (3), 1053–1074 (2017).
     
  21. T. Klimošová, J. Malík, T. Masařík, J. Novotná, D. Paulusma, and V. Slívová, Colouring ($P_r + P_s$)-free graphs, Algorithmica 82 (7), 1833–1858 (2020).
     
  22. D. Král’, J. Kratochvíl, Z. Tuza, and G. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs, in Proc. 27th Int. Workshop Graph-Theoretic Concepts in Computer Science, Boltenhagen, Germany, June 14–16, 2001 (Springer, Heidelberg, 2001), pp. 254–262 (Lect. Notes Comput. Sci., Vol. 2204).
     
  23. V. V. Lozin and D. S. Malyshev, Vertex coloring of graphs with few obstructions, Discrete Appl. Math. 216, 273–280 (2017).
     
  24. D. S. Malyshev, The coloring problem for classes with two small obstructions, Optim. Lett. 8 (8), 2261–2270 (2014).
     
  25. D. S. Malyshev, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Discrete Math. 338 (11), 1860–1865 (2015).
     
  26. D. S. Malyshev, Two cases of polynomial-time solvability for the coloring problem, J. Comb. Optim. 31 (2), 833–845 (2016).
     
  27. D. S. Malyshev, The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs, Graphs Comb. 33 (4), 1009–1022 (2017).
     
  28. D. S. Malyshev, Polynomial-time approximation algorithms for the coloring problem in some cases, J. Comb. Optim. 33, 809–813 (2017).
     
  29. D. S. Malyshev, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, Discrete Appl. Math. 47, 423–432 (2018).
     
  30. D. S. Malyshev, The vertex colourability problem for {claw, butterfly}-free graphs is polynomial-time solvable, Optim. Lett. 15 (2), 311–326 (2021).
     
  31. D. S. Malyshev and O. O. Lobanova, Two complexity results for the vertex coloring problem, Discrete Appl. Math. 219, 158–166 (2017).
     
  32. D. S. Malyshev and O. V. Pristavchenko, An intractability result for the vertex 3-colourability problem, Optim. Lett. 16, 1403–1409 (2022).
     
  33. D. S. Malyshev, O. O. Razvenskaya, and P. M. Pardalos, The computational complexity of weighted vertex coloring for {$P_5, K_{2,3}, K^+_{2,3}$ }-free graphs, Optim. Lett. 15 (1), 137–152 (2021).
     
  34. O. O. Razvenskaya and D. S. Malyshev, Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes, Diskretn. Anal. Issled. Oper. 28 (1), 15–47 (2021) [Russian] [J. Appl. Ind. Math. 15 (1), 97–117 (2021)].
     
  35. D. V. Sirotkin and D. S. Malyshev, On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size, Diskretn. Anal. Issled. Oper. 25 (4), 112–130 (2018) [Russian] [J. Appl. Ind. Math. 12 (4), 759–769 (2018)]
     
  36. S. Spirkl, M. Chudnovsky, and M. Zhong, Four-coloring $P_6$-free graphs, in Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms, San Diego, CA, USA, Jan. 6–9, 2019 (SIAM, Philadelphia, PA, 2019), pp. 1239–1256. 
     
  37. A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (Springer, Heidelberg, 2003) (Algorithms Comb., Vol. 24).
     
  38.  M. Kamiński and V. V. Lozin, Coloring edges and vertices of graphs without short or long cycles, Contrib. Discrete Math. 2 (1), 61–66 (2007).