Sib. Èlektron. Mat. Izv., 2014, Volume 11, Pages 811–822
This article is cited in 3 scientific papers (total in 3 papers)
Discrete mathematics and mathematical cybernetics
The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
D. S. Malyshevab
a Lobachevsky State University of Nizhny Novgorod, 23 Gagarina Avenue, Nizhny Novgorod, 603950, Russia
b National Research University Higher School of Economics,
25/12 Bolshaja Pecherskaja Ulitsa, Nizhny Novgorod, 603155, Russia
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.
computational complexity, edge 3-colorability, hereditary class, efficient algorithm.
PDF file (542 kB)
MSC: 05C15, 05С85
Received November 30, 2013, published November 12, 2014
D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Sib. Èlektron. Mat. Izv., 11 (2014), 811–822
Citation in format AMSBIB
\paper The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
\jour Sib. \`Elektron. Mat. Izv.
Citing articles on Google Scholar:
Related articles on Google Scholar:
This publication is cited in the following articles:
D. S. Malyshev, “Complexity classification of the edge coloring problem for a family of graph classes”, Discrete Math. Appl., 27:2 (2017), 97–101
D. S. Malyshev, O. O. Lobanova, “Two complexity results for the vertex coloring problem”, Discret Appl. Math., 219 (2017), 158–166
E. Galby, P. T. Lima, D. Paulusma, B. Ries, “Classifying k-edge colouring for h-free graphs”, Inf. Process. Lett., 146 (2019), 39–43
|Number of views:|