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/

[1] Vizing, V. G., “Ob otsenke khromaticheskogo klassa $p$-grafa”, Diskretnyi analiz, 3 (1964), 25–30 | MR

[2] Malyshev, D. S., “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. elektr. matem. izv., 11 (2014), 811–822 | Zbl

[3] Boliac, R., Lozin, V. V., “On the clique-width of graphs in hereditary classes”, Lect. Notes Comput. Sci., 2518 (2002), 44–54 | DOI | MR | Zbl

[4] Broersma, H. J., Golovach, P. A., Paulusma, D., Song, J., “Updating the complexity status of coloring graphs without a fixed induced linear forest”, Theor. comput. sci., 414:1 (2012), 9–19 | DOI | MR | Zbl

[5] Courcelle, B., Makowsky, J., Rotics, U., “Linear time solvable optimization problems on graphs of bounded clique-width”, Theory of Comput. Syst., 33:2 (2000), 125–150 | DOI | MR | Zbl

[6] Golovach, P. A., Paulusma, D., Song, J., “4-coloring $H$-free graphs when $H$ is small”, Discrete Appl. Math., 161:1–2 (2013), 140–150 | DOI | MR | Zbl

[7] Gurski, F., Wanke, E., “Line graphs of bounded clique-width”, Discrete Mathematics, 307:22 (2007), 2734–2754 | DOI | MR | Zbl

[8] Kobler, D., Rotics, D., “Edge dominating set and colorings on graphs with fixed clique-width”, Discrete Appl. Math., 126:2–3 (2003), 197–223 | DOI | MR

[9] Lozin, V. V., Kaminski, M., “Coloring edges and vertices of graphs without short or long cycles”, Contrib. to Discr. Math., 2(1) (2007) | MR

[10] Malyshev, D. S., “The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs”, Discrete Math., 338:11 (2015), 1860–1865 | DOI | MR | Zbl

[11] Randerath, B., Schiermeyer, I., Tewes, M., “Three-colourability and forbidden subgraphs. II: polynomial algorithms”, Discrete Math., 251:1–3 (2002), 137–153 | DOI | MR | Zbl

[12] Roussopoulos, N., “A $\max\{m,n\}$ algorithm for determining the graph $H$ from its line graph $G$”, Inf. Process. Lett., 2:4 (1973), 108–112 | DOI | MR | Zbl

[13] Schrijver A., Combinatorial optimization — polyhedra and efficiency, Springer, Berlin, 2003, 1882 pp. | Zbl