12.1. Хроматическое число

Способ явного выражения хроматического числа через другие инварианты графа неизвестен. Известны только некоторые оценки, часть из которых приведена в данном разделе.

Раскраской графа называется такое приписывание цветов (натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет. Наименьшее возможное число цветов в раскраске называется хроматическим числом и обозначается \(G). Очевидно, что существует та-раскраска графа G для любого m в диапазоне \(G) < т ^ р. Множество вершин, покрашенных в один цвет, называется одноцветным классом. Одноцветные классы образуют независи­мые множества вершин, то есть никакие две вершины в одноцветном классе не смежны.

Пример

Х(К_Р} = 1, х(К_р)=р, х(К_т,_п)=2, = 3, _Х(Т) = 2, где Т — свободное дерево.

ТЕОРЕМА _X(G) ^ 1 + Д(С).

один цвет в A(G) + 1 раскраске графа G - v свободен для и. Покрасив v в этот цвет, имеем A(G) + 1 раскраску G. ⁿ

ТЕОРЕМА

x(G) <р- Po(G] + 1.

доказательство

1. Пусть x(G) = п и V = Vi U • • • UV_n, где Vi — одноцветные классы. независимое множество вершин, значит, |Vj| < /?o(G). Имеем:

2. Пусть 5 С V — наибольшее независимое множество, |5| = /3_Q(G). Тогда x(G-S) ^ |V — 5| = р - /?o(G). Из n-раскраски G - 5 можно получить (п + 1)-раскраску G, так как все вершины из 5 можно покрасить в один новый цвет. Следовательно,

ТЕОРЕМА Пусть x-=x(G),X- = x(G). Тогда