Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 29, No 2, 2022, P. 38-61
UDC 519.17
D. S. Malyshev and O. I. Duginov
Some cases of polynomial solvability for the edge colorability problem generated by forbidden 8-edge subcubic forests
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.
Keywords: monotone class, edge-coloring problem, computational complexity.
DOI: 10.33048/daio.2022.29.721
Dmitry S. Malyshev1
Oleg I. Duginov2
1. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
2. Belarusian State University,
4 Nezavisimost Avenue, 220030 Minsk, Belarus
e-mail: dsmalyshev@rambler.ru, oduginov@gmail.com
Received July 7, 2021
Revised February 4, 2022
Accepted February 7, 2022
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. Kaminski 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).
