Файл:Complete coloring clebsch graph.svgПолная раскраска графа Клебша восемью цветами. Каждая пара цветов появляется по меньшей мере на одном ребре. Никаких полных раскрасок с большим числом цветов не существует — при любой раскраске в 9 цветов некоторые цвета могут появиться только на одной вершине, и соседних вершин не хватит, чтобы вовлечь все пары цветов. Таким образом, ахроматическое число графа Клебша равно 8.
В теории графовполная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин, в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(G) графа G — это максимальное число цветов среди всех полных раскрасок графа G.
ДАНО: Граф <math>G=(V,E)</math> и положительное целое число <math>k</math>
ВОПРОС: Существует ли разбиение множества вершин <math>V</math> на <math>k</math> или более непересекающихся множеств <math>V_1,V_2,\ldots,V_k</math> таких, что каждое <math>V_i</math> является независимым множеством для <math>G</math> и таких, что для каждой пары различных множеств <math>V_i,V_j,V_i \cup V_j</math> независимым множеством не является.
Определение ахроматического числа является NP-трудной. Определение, не будет ли ахроматическое число больше заданного числа является NP-полной, как показали Янакакис и Гаврил (Yannakakis, Gavril) в 1978 году путём преобразования из задачи поиска минимального наибольшего паросочетания[1].
Заметим, что любая раскраска графа с минимальным числом цветов должна быть полной раскраской, так что минимизация числа цветов полной раскраски является просто переформулировкой стандартной задачи раскраски графа.
Для дополнений деревьев ахроматическое число может быть вычислено за полиномиальное время[6]. Для деревьев можно задачу аппроксимировать с постоянным коэффициентом[2].
Известно, что ахроматическое число n-мерного графа гиперкуба пропорционально <math>\sqrt{n2^n}</math>, но точная константа пропорциональности не известна[7].
