Повне розфарбування

У теорії графів повне розфарбування — це протилежність гармонійному розфарбуванню в тому сенсі, що це розфарбування вершин, у якому кожна пара кольорів зустрічається принаймні на одній парі суміжних вершин. Еквівалентно, повне розфарбування — це мінімальне розфарбування, в тому сенсі, що його не можна перетворити на правильне розфарбування з меншим числом кольорів злиттям двох кольорів. Ахроматичне число $\psi (G)$ графа $G$ — це найбільше число кольорів серед усіх повних розфарбувань графа $G$.

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

Теорія складності

Знаходження $\psi (G)$ є задачею оптимізації. Проблему розв'язності для повного розфарбування можна сформулювати як:

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

Питання: Чи існує розбиття множини вершин $V$ на $k$ або більше неперетинних множин $V_{1},V_{2},\ldots ,V_{k}$ таких, що кожне $V_{i}$ є незалежною множиною для $G$ і таких, що для кожної пари різних множин $V_{i},V_{j},V_{i}\cup V_{j}$ незалежною множиною не є.

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

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

Алгоритм

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

Окремі випадки графів

Задача визначення ахроматичного числа залишається NP-повною також для деяких класів графів: двочасткових графів, доповнення двочасткових графів (тобто, графи, які не мають незалежної множини з більш ніж двома вершинами), кографи, інтервальні графи і навіть дерева.

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

Відомо, що ахроматичне число n-вимірного графа гіперкуба пропорційне ${\sqrt {n2^{n}}}$, але точний коефіцієнт пропорційності невідомий.

Див. також

• Гармонійне розфарбування
• Тотальне розфарбування
• Т-розфарбування

Посилання

• A compendium of NP optimization problems Архівовано травень 10, 2014 на сайті Wayback Machine.
• A Bibliography of Harmonious Colourings and Achromatic Number Кейта Едвардса