Розфарбуванням простого графу 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 у вигляді суми хроматичних поліномів повних графів.
Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.
