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

Математические заметки. 2026. Т. 119. № 3. С. 360–376.

Дахно Г. С., Малышев Д. С.

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

В данной работе для задачи 3-ВР рассматривается вопрос о полной классификации алгоритмической сложности для пар порожденных запретов с 6 вершинами. Известно, что задача 3-ВР будет NP-полной для такого класса, если ни один элемент пары не будет лесом, и что она будет полиномиальной разрешимой, если один из запретов является линейным лесом. В этой работе рассмотрены четыре нелинейных 6-вершинных леса и получены классификации сложности задачи 3-ВР для всех соответствующих пар.

Ключевые слова: наследственный класс, вычислительная сложность, задача о вершинной 3-раскраске

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Сетевые и графовые модели, сложность алгоритмов и интеллектуальный анализ данных (2025)