Geodesic
A complete complexity dichotomy of~the~edge-coloring problem for~all~sets~of~8-edge forbidden subgraphs
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 4, pp. 91-109

Voir la notice de l'article provenant de la source Math-Net.Ru

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. Illustr. 2, bibliogr. 38.
Keywords: edge-coloring problem, computational complexity
Mots-clés : monotone class. 
@article{DA_2023_30_4_a4,
     author = {D. S. Malyshev and O. I. Duginov},
     title = {A complete complexity dichotomy of~the~edge-coloring problem for~all~sets~of~8-edge forbidden subgraphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {91--109},
     publisher = {mathdoc},
     volume = {30},
     number = {4},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2023_30_4_a4/}
}
TY  - JOUR
AU  - D. S. Malyshev
AU  - O. I. Duginov
TI  - A complete complexity dichotomy of~the~edge-coloring problem for~all~sets~of~8-edge forbidden subgraphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2023
SP  - 91
EP  - 109
VL  - 30
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2023_30_4_a4/
LA  - ru
ID  - DA_2023_30_4_a4
ER  - 
%0 Journal Article
%A D. S. Malyshev
%A O. I. Duginov
%T A complete complexity dichotomy of~the~edge-coloring problem for~all~sets~of~8-edge forbidden subgraphs
%J Diskretnyj analiz i issledovanie operacij
%D 2023
%P 91-109
%V 30
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2023_30_4_a4/
%G ru
%F DA_2023_30_4_a4
D. S. Malyshev; O. I. Duginov. A complete complexity dichotomy of~the~edge-coloring problem for~all~sets~of~8-edge forbidden subgraphs. Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 4, pp. 91-109. http://geodesic.mathdoc.fr/item/DA_2023_30_4_a4/