Розфарбовування графів
Розфарбуванням простого графу 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. Коефіцієнт kn дорівнює 1, а при kn-1 дорівнює m, де m — кількість ребер графу G; знаки коефіцієнтів чергуються; вільний член хроматичного полінома дорівнює 0. Хроматичний поліном будують на основі теореми 3.19 у вигляді суми хроматичних поліномів повних графів.
Див. також
Література
- Ю. В. Нікольський, В. В. Пасічник, Ю. М. Щербина «Дискретна математика», 2007.