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

Доведення. Нехай ((Gr)=k. Тоді правильне k-розфарбування дає розбиття множини V на k однокольорових класів V1,V2,…,Vk. Ясно, що кожен з цих класів є незалежною підмножиною. Оскільки

n=|V1|+|V2|+…+|Vk|( k((Gr),

то ((Gr)( n/((Gr).

Для доведення верхньої оцінки виберемо незалежну підмножину S(V, що містить ((Gr) елементів. Легко помітити, що ((Gr[V\S])( ((Gr)-1. Оскільки |V\S|=n-((Gr), то ((Gr[V\S])(. n-((Gr). Звідси випливає, що

((Gr)(((Gr[V\S])+1( n-((Gr)+1.

Викладемо алгоритм Єршова-Кожухіна розфарбування скінченного графа, що приводить до оцінки його хроматичного числа через кількість вершин і ребер графа. В основі цього алгоритму лежить принцип склеювання вершин і зведення початкового графу до графу з меншим числом вершин.

Надалі в цьому параграфі всі графи вважаються скінченними. Для вершини v графа Gr(V,E) покладемо

S1(v)={x(V: d(v,x)=1}, S2(v)={y(V: d(v,y)=2}.

Склеювання вершин v1, v2 графа - це перетворення з двох кроків. На першому кроці видаляються вершини v1, v2 разом з усіма інцидентними до них ребрами. На другому кроці вибирається нова вершина v (V і сполучається ребрами з усіма вершинами із V\{v1,v2}, з якими були сполучені ребрами вершини v1, v2. В результаті склеювання число вершин зменшується на одиницю, а число ребер не зростає.

Правильне розфарбування множини вершин графа Gr в ((Gr) кольорів називається мінімальним розфарбуванням. Дві вершини графа називаються спорідненими, якщо існує мінімальне розфарбування, при якому ці вершини однокольорові.

Лема 1. Кожен граф Gr(V,E), відмінний від повного графа, має принаймні одну пару споріднених вершин.

Доведення. Нехай |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) непорожня, то знайдеться вершина u(S2(v) , споріднена з вершиною v.

Доведення. Зафіксуємо деяке мінімальне розфарбування графа Gr. Нехай при цьому вершина v пофарбована кольором (. Якщо деяка вершина з S2(v) теж кольору (, лему доведено. Припустимо, що в множині S2(v) немає вершин кольору (. Візьмемо довільну вершину u(S2(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.

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