Полная сложностная дихотомия для запрещённых подграфов с 7 рёбрами в задаче о хроматическом индексе

Задача о рёберной раскраске для заданного графа состоит в том, чтобы минимизировать количество цветов, достаточное для окрашивания его рёбер так, чтобы соседние рёбра были окрашены в разные цвета. Для всех классов графов, определяемых запрещением подграфов с не более чем 6 рёбрами каждый, известен сложностной статус этой задачи. В настоящей работе данный результат улучшается и получена полная классификация сложности задачи о рёберной раскраске для всех множеств запретов, каждый из которых имеет не более чем 7 рёбер. Ил. 3, библиогр. 36.