A Complete Complexity Dichotomy of the Edge-Coloring Problem for All Sets of $$8$$-Edge Forbidden Subgraphs
Dmitriy Sergeevich Malyshev, О. И. Дугинов · Journal of Applied and Industrial Mathematics · 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.