Розфарбовування графів

Розфарбовування графу Петерсена трьома кольорами.

Розфарбуванням простого графу G називають таке приписування кольорів (або натуральних чисел) його вершинам, що ніякі дві суміжні вершини не набувають однакового кольору. Найменшу можливу кількість кольорів у розфарбуванні називають хроматичним числом.

Теорема

Якщо найбільший зі степенів вершини графу дорівнює p, то цей граф можна розфарбувати в p+1 колір.

Доведення

Застосуємо індукцію за кількістю вершин графу. Нехай граф G має n вершин; вилучимо з нього довільну вершину u разом з усіма інцидентними їй ребрами. Отримаємо граф з n-1 вершиною, степінь кожної вершини не більший ніж p. За припущенням індукції цей граф можна розфарбувати в p+1 колір. Отже, у p+1 колір можна розфарбувати й граф G, якщо розфарбувати вершину u кольором, що відрізняється від тих, якими розфарбовано суміжні з нею вершини (а їх разом не більше ніж p).

Теорема Р. Хейвуда

Будь-який планарний граф можна розфарбувати в п'ять кольорів, тобто χ(G)≤5 для будь-якого планарного графу G.

Доведення

Доведення цієї теореми ґрунтується на тому, що в будь-якому простому планарному графі є вершина, степінь якої не більший ніж п'ять. Застосуємо математичну індукцію за кількістю вершин графу. Теорема справджується для графів із не більше ніж n вершинами, де n≥5. Розглянемо довільний плоский граф G з (n+1) вершиною. Він містить вершину u_0, степінь якої не більший ніж п'ять. Нехай W =Г(u_0)- множина вершин, суміжних із вершиною u_0 в графі G. Розглянемо наступний випадок. | W |≤4. Позначимо як G — u_0 граф, отриманий із графу G вилученням вершини u_0 та всіх інцидентних їй ребер. За індуктивним припущенням граф G — u_0 можна розфарбувати в п'ять кольорів. Зафіксуємо одне з таких розфарбувань і зафарбуємо вершину u_0 в той із п'яти кольорів, який не використано для фарбування вершин із множини W.

Теорема

Нехай G — простий граф, а u та w — його несуміжні вершини. Якщо граф G_1 отримано з G за допомогою з'єднання вершин u та wребром, а граф G_2 — ототожненням вершини u та w (і кратних ребер, якщо їх буде одержано), то P_G(k)=P_G1(k)+P_G2(k).

Доведення

За будь-якого допустимого розфарбовування вершин графу G існує альтернатива: u та w мають різні кольори, або той самий. Кількість розфарбовувань, за яких u та w мають різні кольори, не зміниться, якщо долучити ребро {u, w}. Отже, ця кількість дорівнює P_G1(k). Аналогічно, кількість розфарбовувань, за яких u та w мають один колір, не зміниться, якщо ототожнити u та w. Залишилось застосувати комбінаторне правило суми. Теорему доведено.

Наслідок

Хроматична функція простого графу — поліном. P_G(k) — хроматичний поліном .Якщо граф G має n вершин, то степінь полінома P_G(k) дорівнює n. Коефіцієнт kⁿ дорівнює 1, а при k^n-1 дорівнює m, де m — кількість ребер графу G; знаки коефіцієнтів чергуються; вільний член хроматичного полінома дорівнює 0. Хроматичний поліном будують на основі теореми 3.19 у вигляді суми хроматичних поліномів повних графів.

Див. також

• Жадібне розфарбовування
• Колове розфарбовування
• Мичельськіан
• Ніде не нульовий потік
• Однозначно розфарбовуваний граф
• Проблема чотирьох фарб
• Теорема де Брейна — Ердеша (теорія графів)
• Хроматичне число
• Цілком упорядковуваний граф

Література

• Ю. В. Нікольський, В. В. Пасічник, Ю. М. Щербина «Дискретна математика», 2007.