Полная классификация сложности задачи о вершинной 3-раскраске для четверок порожденных 5-вершинных запретов

Задача о вершинной 3-раскраске для заданного графа состоит в том, чтобы проверить, возможно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Наследственный класс графов — множество обыкновенных графов, замкнутое относительно изоморфизма и удаления вершин. Любой такой класс может быть задан множеством своих запрещенных порожденных подграфов. Известен сложностной статус задачи о вершинной 3-раскраске для всех четверок 5-вершинных запрещенных порожденных подграфов, кроме трех из них. Более того, известно, что два из этих трех случаев полиномиально эквивалентны и полиномиально сводятся к третьему. В настоящей работе доказывается, что вычислительная сложность рассматриваемой задачи во всех трех упомянутых классах является полиномиальной. Данный результат вносит вклад в алгоритмическую теорию графов.