Некоторые классификации сложности задачи о вершинной 3-раскраске

Наследственный класс – множество графов, замкнутое относительно удаления вершин. Каждый такой класс имеет каноническое описание посредством минимальных запрещенных порожденных фрагментов. Задача о вершинной 3-раскраске (задача 3-$\mathrm{BP}$) для заданного графа состоит в том, чтобы определить, а можно ли множество его вершин разбить на три подмножества попарно несмежных вершин. Известна дихотомия сложности этой задачи для всех наследственных классов, определяемых 5-вершинными порожденными запретами. В данной работе для задачи 3-$\mathrm{BP}$ рассматривается вопрос о полной классификации алгоритмической сложности для пар порожденных запретов с 6 вершинами. Известно, что задача 3-$\mathrm{BP}$ будет NP-полной для такого класса, если ни один элемент пары не будет лесом, и что она будет полиномиальной разрешимой, если один из запретов является линейным лесом. В этой работе рассмотрены четыре нелинейных 6-вершинных леса и получены классификации сложности задачи 3-$\mathrm{BP}$ для всех соответствующих пар.
Библиография: 21 название.