О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами

О случаях полиномиальной разрешимости задачи о рёберной раскраске, порождаемых запрещёнными 8-рёберными субкубическими лесами

Малышев Д. С., Дугинов О. И.
Дискретный анализ и исследование операций, 29, 2, 38-61 (2022)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2022.29.721

Аннотация:

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

Литература:
  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. 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.
     
  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).

Исследование выполнено за счёт

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

E-mail: dsmalyshev@rambler.ru

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

E-mail: oduginov@gmail.com

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

Abstract:

The edge-coloring problem, is to minimize the number of colors sufficient to color all the edges of a given graph so that any adjacent edges receive distinct colors. For all the classes defined by sets of forbidden subgraphs with 7 edges each, the complexity status of this problem is known. In this paper, we consider the case of prohibitions with 8 edges. It is not hard to see that the edge-coloring problem is NP-complete for such a class if there are no subcubic forests among its 8-edge prohibitions. We prove that forbidding any subcubic 8-edge forest generates a class with polynomial-time solvability of the edgecoloring problem, except for the cases formed by the disjunctive sum of one of 4 forests and an empty graph. For all the remaining four cases, we prove a similar result for the intersection with the set of graphs of maximum degree at least four. 
Illustr. 2, bibliogr. 14.

References:
  1. I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 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, 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. Mat. 14 (4), 706–721 (2020)].
     
  7. 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).
     
  8. A. Schrijver, Combinatorial Optimization. Polyhedra and Efficiency (Springer, Heidelberg, 2003).
     
  9. B. Courcelle, J. A. Makowsky, and U. Rotics, Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst. 33 (2), 125–150 (2000).
     
  10. F. Gurski and E. Wanke, Line graphs of bounded clique-width, Discrete Math. 307 (22), 2734–2754 (2007).
     
  11. D. Kobler and U. Rotics, Edge dominating set and colorings on graphs with fixed clique-width, Discrete Appl. Math. 126 (2–3), 197–223 (2003).
     
  12. R. Boliac and V. V. Lozin, On the clique-width of graphs in hereditary classes, in Algorithms and Computation (Proc. 13th Int. Symp., Vancouver, Canada, Nov. 21–23, 2002) (Springer, Heidelberg, 2002), pp. 44–54 (Lect. Notes Comput. Sci., Vol. 2518).
     
  13. D. Corneil and U. Rotics, On the relationship between clique-width and treewidth, SIAM J. Comput. 34 (4), 825–847 (2005).
     
  14. F. Gurski and E. Wanke, The tree-width of clique-width bounded graphs without $K_{n,n}$, in Graph-Theoretic Concepts in Computer Science (Proc. 26th Int. Workshop, Konstanz, Germany, June 15–17, 2000) (Springer, Heidelberg, 2000), pp. 196–205 (Lect. Notes Comput. Sci., Vol. 1928).