RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2022 Volume 29, Issue 2, Pages 38–61 (Mi da1297)

This article is cited 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.

UDC: 519.17

Received: 07.07.2021
Revised: 04.02.2022
Accepted: 07.02.2022

DOI: 10.33048/daio.2022.29.721



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024