§ 6 Хроматичні і калейдоскопічні числа

Нехай Gr(V,E) - граф, k - кардинал. Правильним k-розфарбуванням графа Gr(V,E) називається розфарбування c: V®k, таке що будь-які дві суміжні вершини різнокольорові. Хроматичним числом графа Gr називається найменший кардинал k, для якого існує правильне k–розфарбування. Хроматичне число графа Gr позначається c(Gr). Якщо c(Gr)=k, то граф Gr називається k–хроматичним. Очевидно, що c(Gr)=1 тоді і тільки тоді, коли E(Gr)=Æ.

Відмітимо, що c(Gr)=2 тоді і тільки тоді, коли множина вершин V(Gr) є 2-розкладною відносно множини E(Gr) усіх ребер графа.

Розглянемо хроматичні числа графів з точки зору корозкладності.

Нехай X – довільна непорожня множина, Á - деяка сім’я підмножин множини X, k - кардинал. Множина X називається k–корозкладною відносно сім’ї Á, якщо існує розбиття X на k підмножин, таке що FËA для кожної підмножини FÎÁ і кожної підмножини A розбиття. В хроматичній термінології множина X являється k–корозкладною відносно сім’ї Á, якщо існує k-розфарбування X, таке що жодна підмножина FÎÁ не є однокольоровою. Припустимо, що сім’я Á не містить одноелементних підмножин і порожньої підмножини. Тоді X являється |X|–корозкладною відносно сім’ї Á. Найменший кардинал k, для якого множина X являється k–корозкладною відносно сім’ї Á, називається показником корозкладності X відносно Á.

Таким чином, хроматичне число графа Gr – це показник корозкладності множини його вершин відносно сім’ї його ребер.

Послідовність x₁,x₂,…,x_n, n³3 різних вершин графа Gr(V,E) називається циклом, якщо

(x₁,x₂)ÎE, (x₂,x₃)ÎE,…,(x_n-1,x_n)ÎE, (x₁,x_n)ÎE.

Цикл називається парним (непарним), якщо число n парне (непарне).

Задача 6.1. Довести, що хроматичне число парного циклу дорівнює 2, а непарного – 3.

Теорема 6.1. Хроматичне число графа Gr(V,E) дорівнює 2 тоді і тільки тоді, коли E¹Æ і граф не має непарних циклів.

Доведення. Необхідність випливає із задачі 6.1. При доведенні достатності можна вважати, що граф Gr(V,E) зв'язний і |V|³ 2. Зафіксуємо довільний кістяк Tr(V,E') графа Gr(V,E), E'ÍE. Візьмемо довільну вершину xÎV і покладемо c(x)=0. Для кожної вершини y ÎV покладемо c(y)=0 (c(y)=1) тоді і тільки тоді, коли відстань від x до y в дереві Tr(V,E') парна (непарна). Таким чином, визначено деяке розфарбування c: V®{0,1}. Візьмемо довільне ребро (y,z)ÎE. Якщо (y,z)ÎE', то c(y)¹c(z) за означенням відображення c. Припустимо, що (y,z)ÏE'. Тоді знайдеться вершина vÎV, така що через вершини y,z,v проходить деякий цикл

v₁,v₂,…,v_n,v_n+1,…,v_m

де v₁=v, v_n=y, v_n+1=z, (v_m,v)ÎE. Оскільки число m парне, то c(y)¹c(z).

Характеризація k-хроматичних графів для k³3 невідома. Більше того, обчислення хроматичних чисел деяких природних класів графів може виявитись досить тонкою проблемою. У цьому зв'язку пригадаємо знамениту проблему чотирьох фарб. Ми обмежимося лише оцінками хроматичного числа графа через простіші його інваріанти.

Позначимо через r (x) локальний степінь вершини x графа Gr(V,E) і покладемо r (Gr)= sup {r (x): xÎV}.

Теорема 6.2. Якщо число r (Gr) скінченне, то c (Gr)£ r (Gr)+1.

Доведення. Спочатку припустимо, що граф Gr(V,E) скінченний і застосуємо індукцію по числу його вершин. Для |V|=1 твердження очевидне. Розглянемо довільний скінченний граф Gr(V,E), |V|>1 і зафіксуємо деяку його вершину x. Видалимо з графа Gr(V,E) вершину x і всі ребра (x,y₁), (x,y₂),…,(x,y_m), що виходять з цієї вершини. Одержаний граф позначимо Gr'(V',E'). Оскільки r (Gr') £ r (Gr) і |V'|<|V|, то за припущенням індукції існує відображення c: V'®{1,2,…,r(Gr)+1}, таке що c(y)¹c(z) для кожного ребра (y,z)ÎE'. Оскільки m<r(Gr)+1, то знайдемо число

iÎ{1,2,…,r(Gr)+1}\{c(y₁),c(y₂),…,c(y_m)}

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

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

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

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

Теорема 6.3. Нехай Gr(V,E) - скінченний граф, V={v₁,v₂,…,v_n}, r(v₁)³r(v₂)³…³r(v_n).Тоді

c(Gr) £

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

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

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

n/b(Gr) £ c(Gr)£ n-b(Gr) +1.

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

n=|V₁|+|V₂|+…+|V_k|£ kb(Gr),

то c(Gr)³ n/b(Gr).

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

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

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

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

S₁(v)={xÎV: d(v,x)=1}, S₂(v)={yÎV: d(v,y)=2}.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(i) c (Gr)£ ;

(ii) c (Gr)³ .

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

|V(Gr_s )|=c (Gr_s )=c (Gr)=n-s

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

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

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

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

Розв'яжемо цю нерівність відносно c (Gr) і одержимо

c (Gr)£ (3+/2.

Доведемо нижню оцінку (іі). Позначимо c (Gr)=k. Назвемо відсутнім ребром (v_q,v_p) в графі Gr будь-яку упорядковану пару несуміжних вершин, а також усі пари (v_q,v_q). Очевидно, що кількість відсутніх ребер дорівнює n² -2m. Зафіксуємо деяке мінімальне розфарбування графа Gr. Нехай X_i - множина усіх вершин кольору i, n_i=|X_i|, iÎ{1,2,…,k}. Оскільки усі вершини множини X_i попарно несуміжні, то загальне число відсутніх ребер, утворених лише вершинами з X_i , дорівнює n_i². Звідси випливає нерівність

£ n^2 -2m

(1)

за додаткової умови

= n.

(2)

Знайдемо мінімум p функції F= за умови (2) на множині цілих чисел. Для цього покладемо

ni = [n/k]+yi, l=n-[n/k]k,

(3)

де n/k - значення n_i, що мінімізує функцію F за умови (2) на множині раціональних чисел. Очевидно, що

= l, 0£ l£ k.

(4)

Можна показати, що знаходження мінімуму функції F за умови (2) зводиться до знаходження мінімуму функції за умови (4). Цей мінімум досягається, наприклад, при

y₁=y₂=…=y_k-l=0, y_k-l+1=…=y_k=1.

Звідси випливає, що

p=n^2/k+k(n/k-[n/k])(1+[n/k]-n/k),

(5)

де n²/k - мінімум функції F на множині раціональних чисел. Отже, нерівність (1) можна переписати у такому вигляді

k^2(n/k-[n/k])(1+[n/k]-n/k)£ (n^2-2m)k-n^2

(6)

З цієї нерівності випливає, що

c(Gr)³ -[-x0],

(7)

де x₀ - корінь рівняння

x^2(n/x-[n/x])(1+[n/x]-n/x)£ (n^2-2m)x-n^2

(8)

що лежить на відрізку від 1 до n.

Досліджуючи поведінку лівої та правої частин рівняння (8), можна показати, що [n/x₀]=[n/x₁], де x₁ - корінь рівняння

(n²-2m)x-n²=0.

Обчислимо [n/x₁] і поставимо його в (8). Одержимо лінійне рівняння відносно x, з якого знаходимо

x₀ =.

Враховуючи (7), одержуємо оцінку (іі).

Наступний приклад показує, що верхня оцінка (і) в теоремі 6.5 є точною.

Приклад 6.1. Побудуємо зв'язний граф Gr з n вершинами і m ребрами, для якого c(Gr)=l , де

l=[(3+) ¤ 2].

(9)

Очевидно, що число m ребер зв'язного графа з n вершинами задовольняє нерівності

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

Враховуючи (9) одержуємо нерівності

l£ n, l(l-1) /2 £ m, n- l £ m-l(l-1) /2 .

Граф Gr будуємо так: виберемо довільну вершину повного графа з l вершинами і приєднаємо до неї ланцюг з n-l вершинами і n-l ребрами, а решту

m-l(l-1) /2 -(n-l)

ребер визначаємо довільним чином. Оскільки граф Gr містить повний граф з l вершинами, то c(Gr)³ l . З нерівності (і) випливає, що c(Gr)£ l. Отже, c(Gr)= l.

Розглянемо довільний граф Gr(V,E). Калейдоскопічним число графа Gr(V,E) називається найменший кардинал k(Gr), для якого існує розфарбування c: V® k(Gr), таке що в кожній кулі B(x,1), xÎV немає двох однокольорових вершин. Зрозуміло, що r(Gr)+1£ k(Gr) £. |V|. Побудуємо допоміжний граф Gr'(V,E'), де E' - множина усіх пар різних вершин із V, відстань між якими в графі Gr(V,E) не перевищує 2.

Задача 6.3. Довести, що k(Gr)=c(Gr').

Задача 6.4. Довести, що k(Gr)£ r (Gr)(r(Gr)-1)+1.

Задача 6.5. Нехай Gr_n - цикл з n вершинами, n³3. Довести, що

k(Gr_n)=

Задача 6.6. Довести, що k (Tr)=r (Tr)+1 для кожного дерева Tr.

Задача 6.7. Довести, що однорідний граф Gr скінченного степеня k калейдоскопічний тоді і тільки тоді, коли k (Gr)=k+1.