Классификация сложности задачи о рёберной раскраске для некоторого семейства классов графов

Класс графов называется монотонным, если он замкнут относительно удалений вершин и рёбер. Любой такой класс может быть задан запрещёнными подграфами. Хроматическим индексом графа называется наименьшее количество цветов, необходимое для такого раскрашивания его рёбер, что любые два соседних ребра имеют разные цвета. В статье получена полная классификация сложности задачи о хроматическом индексе для всех монотонных классов, определяемых запрещёнными подграфами, каждый из которых имеет не более 6 рёбер или не более 7 вершин.
Работа выполнена при поддержке Российского Фонда Фундаментальных Исследований, проект № 16-31-60008-мол_а_дк, гранта Президента РФ МК-4819.2016.1, лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ.