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

Нахождение ψ(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].

• A compendium of NP optimization problems Архивная копия от 10 мая 2014 на Wayback Machine
• A Bibliography of Harmonious Colourings and Achromatic Number by Keith Edwards

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.