Geodesic
The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 811-822

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

We obtain a complete complexity dichotomy for the edge 3-colorability within the family of hereditary classes defined by forbidden induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures.
Keywords: computational complexity, edge 3-colorability, hereditary class
Mots-clés : efficient algorithm. 
@article{SEMR_2014_11_a54,
     author = {D. S. Malyshev},
     title = {The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {811--822},
     publisher = {mathdoc},
     volume = {11},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2014_11_a54/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2014
SP  - 811
EP  - 822
VL  - 11
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2014_11_a54/
LA  - en
ID  - SEMR_2014_11_a54
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2014
%P 811-822
%V 11
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2014_11_a54/
%G en
%F SEMR_2014_11_a54
D. S. Malyshev. The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 11 (2014), pp. 811-822. http://geodesic.mathdoc.fr/item/SEMR_2014_11_a54/