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

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

Відмітимо, що (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 – це показник корозкладності множини його вершин відносно сім’ї його ребер.

Послідовність x1,x2,…,xn, n3 різних вершин графа Gr(V,E) називається циклом, якщо

(x1,x2)E, (x2,x3)E,…,(xn-1,xn)E, (x1,xnE.

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

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

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

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

v1,v2,…,vn,vn+1,…,vm

де v1=v, vn=y, vn+1=z, (vm,v)E. Оскільки число m парне, то (y)(z).

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

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

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

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

i{1,2,…,(Gr)+1}\{(y1),(y2),…,(ym)}