Сильные k-раскраски графов

Abstract

Правильная $k$-раскраска $C_1,\ldots,C_k$ графа $G$ называется сильной, если для любой вершины $u\in VG$ существует индекс $i\in\{1,\ldots,k\}$ такой, что $u$ смежна с каждой вершиной класса $C_i$. В этой работе рассмотрен класс $S(k)$ сильно $k$-раскрашиваемых графов и показано, что задача распознавания $S(k)$ является NP-полной при любом $k\ge4$, а при $k=3$ — полиномиально разрешимой. Мы даем характеризацию класса $S(3)$ в терминах запрещенных порожденных подграфов и решаем проблему единственности сильной 3-раскраски.