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

Не плутати з тотальним розфарбуванням.

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

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

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

Знаходження ${\displaystyle \psi (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].

Див. також

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