О сложности задачи вершинной $3$-раскраски для наследственных классов графов, определённых запретами небольшого размера

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