|
This article is cited in 1 scientific paper (total in 1 paper)
Some cases of polynomial solvability for the edge colorability problem generated by forbidden $8$-edge subcubic forests
D. S. Malysheva, O. I. Duginovb a National Research University “Higher School of Economics”, 25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
b Belarusian State University, 4 Nezavisimost Avenue, 220030 Minsk, Belarus
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 edge-coloring 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.
Keywords:
monotone class, edge-coloring problem, computational complexity.
Received: 07.07.2021 Revised: 04.02.2022 Accepted: 07.02.2022
Citation:
D. S. Malyshev, 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 (2022), 38–61
Linking options:
https://www.mathnet.ru/eng/da1297 https://www.mathnet.ru/eng/da/v29/i2/p38
|
Statistics & downloads: |
Abstract page: | 172 | Full-text PDF : | 28 | References: | 24 | First page: | 5 |
|