Geodesic
Complexity classification of the edge coloring problem for a~family of graph classes
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 44-50

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

A class of graphs is called monotone if it is closed under deletion of vertices and edges. Any such class may be defined in terms of forbidden subgraphs. The chromatic index of a graph is the smallest number of colors required for its edge-coloring such that any two adjacent edges have different colors. We obtain a complete classification of the complexity of the chromatic index problem for all monotone classes defined in terms of forbidden subgraphs having at most 6 edges or at most 7 vertices.
Keywords: computational complexity, chromatic index problem, efficient algorithm. 
@article{DM_2016_28_2_a3,
     author = {D. S. Malyshev},
     title = {Complexity classification of the edge coloring problem for a~family of graph classes},
     journal = {Diskretnaya Matematika},
     pages = {44--50},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a3/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Complexity classification of the edge coloring problem for a~family of graph classes
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 44
EP  - 50
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a3/
LA  - ru
ID  - DM_2016_28_2_a3
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Complexity classification of the edge coloring problem for a~family of graph classes
%J Diskretnaya Matematika
%D 2016
%P 44-50
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a3/
%G ru
%F DM_2016_28_2_a3
D. S. Malyshev. Complexity classification of the edge coloring problem for a~family of graph classes. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 44-50. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a3/