Полная раскраска

Полная раскраска графа Клебша восемью цветами. Каждая пара цветов появляется по меньшей мере на одном ребре. Никаких полных раскрасок с большим числом цветов не существует — при любой раскраске в 9 цветов некоторые цвета могут появиться только на одной вершине, и соседних вершин не хватит, чтобы вовлечь все пары цветов. Таким образом, ахроматическое число графа Клебша равно 8.

В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.

Теория сложности

Нахождение ψ(G) является задачей оптимизации. Проблема разрешимости для полной раскраски может быть сформулирована как:

ДАНО: Граф $G=(V,E)$ и положительное целое число $k$

ВОПРОС: Существует ли разбиение множества вершин $V$ на $k$ или более непересекающихся множеств $V_1,V_2,\dots ,V_k$ таких, что каждое $V_i$ является независимым множеством для $G$ и таких, что для каждой пары различных множеств $V_i,V_j,V_i\cup V_j$ независимым множеством не является.

Определение ахроматического числа является NP-трудной. Определение, не будет ли ахроматическое число больше заданного числа является NP-полной, как показали Янакакис и Гаврил (Yannakakis, Gavril) в 1978 году путём преобразования из задачи поиска минимального наибольшего паросочетания.

Заметим, что любая раскраска графа с минимальным числом цветов должна быть полной раскраской, так что минимизация числа цветов полной раскраски является просто переформулировкой стандартной задачи раскраски графа.

Алгоритм

Оптимизационная задача допускает аппроксимацию с гарантированной эффективностью $O(|V|/\sqrt{\log |V|})$.

Специальные случаи графов

Задача определения ахроматического числа остаётся NP-полной также для некоторых специальных классов графов: двудольные графы, дополнения двудольных графов (то есть, графы, не имеющие независимого множества с более чем двумя вершинами), кографы, интервальные графы и даже деревья.

Для дополнений деревьев ахроматическое число может быть вычислено за полиномиальное время. Для деревьев можно задачу аппроксимировать с постоянным коэффициентом.

Известно, что ахроматическое число n-мерного графа гиперкуба пропорционально $\sqrt{n{2}^n}$, но точная константа пропорциональности не известна.

Ссылки

• A compendium of NP optimization problems Шаблон:Wayback
• A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards