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

Задача о рёберном списковом ранжировании является обобщением классической задачи о раскраске рёбер графа и математической моделью протекания ряда параллельных процессов. В настоящей работе исследуется вычислительная сложность этой задачи для замкнутых относительно изоморфизма и удаления вершин множеств графов (наследственных классов). Описываются все конечно определённые и минорно замкнутые случаи, для которых эта задача полиномиально разрешима. Выявляется вся совокупность “критических” классов графов, включение которых в конечно определённый класс эквивалентно “труднорешаемости” задачи о рёберном списковом ранжировании в этом классе. По-видимому, это вообще первый результат о полном таком описании для неискусственных NP-полных задач на графах. Конструктивно доказывается, что для этой задачи среди минимальных по включению наследственных случаев “труднорешаемости” имеется всего пять конечно определённых классов и один минорно замкнутый класс. Ил. 1, библиогр. 13.