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

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