D. S. Malyshev, “The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices”, Сиб. электрон. матем. изв., 2014, том 11,страницы 811

Эта публикация цитируется в 6 статьях

Дискретная математика и математическая кибернетика

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

Аннотация: 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.

УДК: 519.178

MSC: 05C15, 05С85

Поступила 30 ноября 2013 г., опубликована 12 ноября 2014 г.

Язык публикации: английский