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., 2014, Volume 11,Pages <nobr>811

This article is cited in 6 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. Malyshev^ab

^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

Abstract: 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, efficient algorithm.

UDC: 519.178

MSC: 05C15, 05С85

Received November 30, 2013, published November 12, 2014

Language: English