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

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

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

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

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

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

ВОПРОС: Существует ли разбиение множества вершин ${\displaystyle V}$ на ${\displaystyle k}$ или более непересекающихся множеств ${\displaystyle V_{1},V_{2},\ldots ,V_{k}}$ таких, что каждое ${\displaystyle V_{i}}$ является независимым множеством для ${\displaystyle G}$ и таких, что для каждой пары различных множеств ${\displaystyle V_{i},V_{j},V_{i}\cup V_{j}}$ независимым множеством не является.

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

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

Алгоритм

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

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

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

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

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