Geodesic
Complete complexity dichotomy for~7-edge~forbidden subgraphs in~the~edge~coloring~problem
Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 104-130

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

The edge coloring problem for a graph is to minimize the number of colors that are sufficient to color all edges of the graph so that all adjacent edges receive distinct colors. The computational complexity of the problem is known for all graph classes defined by forbidden subgraphs with at most 6 edges. We improve this result and obtain a complete complexity classification of the edge coloring problem for all sets of prohibitions each of which has at most 7 edges. Illustr. 3, bibliogr. 36.
Keywords: edge coloring problem, strongly hereditary class, computational complexity. 
@article{DA_2020_27_4_a4,
     author = {D. S. Malyshev},
     title = {Complete complexity dichotomy for~7-edge~forbidden subgraphs in~the~edge~coloring~problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {104--130},
     publisher = {mathdoc},
     volume = {27},
     number = {4},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2020_27_4_a4/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Complete complexity dichotomy for~7-edge~forbidden subgraphs in~the~edge~coloring~problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2020
SP  - 104
EP  - 130
VL  - 27
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2020_27_4_a4/
LA  - ru
ID  - DA_2020_27_4_a4
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Complete complexity dichotomy for~7-edge~forbidden subgraphs in~the~edge~coloring~problem
%J Diskretnyj analiz i issledovanie operacij
%D 2020
%P 104-130
%V 27
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2020_27_4_a4/
%G ru
%F DA_2020_27_4_a4
D. S. Malyshev. Complete complexity dichotomy for~7-edge~forbidden subgraphs in~the~edge~coloring~problem. Diskretnyj analiz i issledovanie operacij, Tome 27 (2020) no. 4, pp. 104-130. http://geodesic.mathdoc.fr/item/DA_2020_27_4_a4/