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

і покладемо (x)=i.

Для поширення твердження теореми на нескінченні графи можна скористатися принципом компактності [20, p. 13].

Задача 2. Довести, що (Gr) (Gr), якщо (Gr) - нескінченний кардинал.

Теорема 2. дає досить точну оцінку хроматичного числа за умови, що локальні степені вершин приблизно однакові. Якщо ж граф має вершини, локальні степені вершин якого різко відрізняються, то ця оцінка значно завищена. Наприклад це так для зірки, хроматичне число якої 2. В подібних ситуаціях значно кращу оцінку дає наступна теорема.

Теорема 3. Нехай Gr(V,E) - скінченний граф, V={v1,v2,…,vn}, (v1)(v2)(vn).Тоді

(Gr)

Доведення. Покладемо (v1)=1. Припустимо, що вершини v1, v2,…, vi вже пофарбовано в кольори {1,2,…,n(i)}, n(i) i. Якщо i+1 1(vi+1), покладемо (vi+1)=n(i)+1. Якщо i+1 > 1+(vi+1), виберемо колір з найменшим номером c, що не зустрічається серед кольорів вершин {v1,v2,…,vi}, суміжних з вершиною vi+1, і покладемо (vi+1)=c.

Підмножина A множини вершин графа Gr(V,E) називається незалежною, якщо будь-які дві вершини x,yA несуміжні. Число незалежності (Gr) скінченного графа Gr - це кількість елементів в найбільшій за розмірами незалежній множині цього графа.

Теорема 4. Для будь-якого скінченного графа Gr(V,E), |V|=n справедливі оцінки

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

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

то (Gn/(Gr).

Для доведення верхньої оцінки виберемо незалежну підмножину SV, що містить (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)={xV: d(v,x)=1}, S2(v)={yV: d(v,y)=2}.

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

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

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