В теории графов полная раскраска — это противоположность гармонической раскраске в том смысле, что это раскраска вершин , в которой каждая пара цветов встречается по меньшей мере на одной паре смежных вершин. Эквивалентно, полная раскраска — это минимальная раскраска, в том смысле, что её нельзя преобразовать в правильную раскраску с меньшим числом цветов путём слияния двух цветов. Ахроматическое число ψ(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 году путём преобразования из задачи поиска минимального наибольшего паросочетания .

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

Алгоритм

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

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

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

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

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

Примечания

Ссылки

• от 10 мая 2014 на Wayback Machine
• by Keith Edwards