Розкладність графів. Хроматичні і калейдоскопічні числа

Доведення. Нехай |V|=n. Припустимо, що в деякому мінімальному розфарбуванні графа взагалі немає двох однокольорових вершин. Тоді (Gr)=n. Оскільки граф Gr неповний, то в ньому знайдеться пара v1, v2 несуміжних вершин. Склеїмо ці вершини і одержимо граф Gr' з |V(Gr')|=n-1. Виберемо в ньому вершину v, в яку були склеєні вершини v1, v2. Розклеїмо ці вершини і пофарбуємо їх в колір вершини v. Одержимо правильне розфарбування графа Gr в n-1 кольорів, що суперечить припущенню (Gr)=n.

Лема 2. Якщо граф Gr' отримано з графа Gr склеюванням пари споріднених вершин, то (Gr')=(Gr).

Доведення. Нерівність (Gr')(Gr) очевидна. Нерівність (Gr)(Gr') вірна, якщо склеюється довільна пара несуміжних вершин.

Лема 3 Для будь-якого графа Gr з хроматичним числом k існує послідовність попарних склеювань вершин, що приводить до повного графу з k вершинами.

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

Лема 4. Якщо v - вершина графа Gr(V,E) і множина S2(v) непорожня, то знайдеться вершина uS2(v) , споріднена з вершиною v.

Доведення. Зафіксуємо деяке мінімальне розфарбування графа Gr. Нехай при цьому вершина v пофарбована кольором . Якщо деяка вершина з S2(v) теж кольору , лему доведено. Припустимо, що в множині S2(v) немає вершин кольору . Візьмемо довільну вершину uS2(v), пофарбовану кольором. Розглянемо два випадки.

Якщо в S1(v) немає вершин кольору , то перефарбуємо вершину v кольором .

Припустимо, що множина R усіх вершин із S1(v) кольору непорожня. Перефарбуємо ці вершини кольором , а вершину v - кольором .

Алгоритм Єршова-Кожухіна складається з двох етапів - згортки і розгортки. Спираючись на лему 4 вибираємо пари вершин, відстань між якими дорівнює 2, і склеїмо їх. Згідно з лемою 3 згортка закінчується побудовою повного графа. Розфарбуємо його вершини різними кольорами і розгорткою отримаємо правильне розфарбування початкового графа. При вдалому виборі послідовності склеюваних вершин це розфарбування мінімальне. В загальному випадку одержимо правильне розфарбування, наближене до мінімального.

Застосуємо алгоритм Єршова-Кожухіна для оцінки хроматичного числа. Позначимо через [x] і {x} цілу та дробові частини числа x.

Теорема 5. Для довільного зв'язного графа Gr(V,E), |V|=n, |E|=m справедливі такі оцінки

Доведення. Спочатку доведено верхню оцінку (і). Якщо граф Gr неповний, то за лемою 4 в ньому знайдеться пара споріднених вершин, відстань між якими дорівнює 2. Склеїмо їх і за лемою 2 одержимо граф з тим самим хроматичним числом. Зауважимо, що число вершин цього графа менше на одиницю, а число ребер менше принаймні на одиницю. Повторюючи цю процедуру s
|V(Grs )| (Grs ) (Gr)=n-s

Позначимо через Gr0 , Gr1,…,Grs , Gr0=Gr послідовність графів, що з'явилися в результаті попарних склеювань. Повний граф Grs має (Gr)( (Gr)-1)/2 ребер. Це число на m- (Gr)( (Gr)-1)/2 менше, ніж число ребер графа Gr. Оскільки на кожному кроці граф Gri має принаймні на одне ребро менше, ніж граф Gri-1, то

m (Gr)( (Gr)-1)/2 s.

Таким чином, маємо нерівність

m (Gr)( (Gr)-1)/2 n (Gr).