6.15. Хроматические графы

Пусть простой граф. Граф называется -раскрашиваемым, если существует такое разложение множества его вершин к непересекающихся подмножеств (компонент) таких, что к

и вершины в каждой компоненте -независимы, т.е. ребра в соединяют вершины только из разных компонент (рис. 6.56). Представление (6.15.1) называется -раскраской графа Вершины этого графа можно раскрасить к красками так, чтобы смежные вершины всегда были окрашены в разные цвета. Для этого достаточно вершины каждой компоненты С, покрасить своей краской.

Наименьшее возможное число компонент в разложении (6.15.1) называется хроматическим числом графа

Рассмотрим несколько примеров хроматического разложения графов.

Рис. 6.56

• Утверждение 15.1. Полный граф на вершинах имеет хроматическое число Здесь каждая компонента разложения (6.15.1) состоит из одной вершины,

• Утверждение 15.2. Граф содержит максимальный подграф (клику) из к вершин тогда и только когда, когда его хроматическое число равно k.

Доказательство. Пусть вершины максимального подграфа. Для разложения (6.15.1) максимального подграфа требуется к компонент таких, что Покажем, что этого числа компонент достаточно для разложения (6.15.1) всего графа Пусть произвольная вершина и Среди существует такая вершина которая несмежна с у, в противном случае существовал бы максимальный подграф из к вершины. Вершину у включаем в компоненту Следовательно,

Имеем Предположим, что максимальный подграф в содержит вершин и Необходимое условие теоремы в этом случае утверждает: что противоречит условию.

• Утверждение 15.3. Граф является двудольным тогда и только тогда, когда

Утверждение 15.4. Хроматическое число дерева равно 2, так как дерево является двудольным графом.

• Теорема 6.15.1. Для числа вершинной независимости и хроматического числа графа выполняется соотношение

Доказательство. В разложении (6.15.1) все компоненты С, являются независимыми. Из определения числа следует, что

Суммируя по всем компонентам, получим где

Рис. 6.57

Задача. Для графа рис. 6.57 найти разложение (6.15.1) и установить, что хроматическое число

Задача. Пусть длина самой длинной простой цепи в графе Показать, что

Решение. Предположим, что Тогда утверждение 15.2 позволяет сделать заключение, что граф содержит максимальный подграф (клику) из вершин или более. Такой подграф содержит простой цикл из ребер и простую цепь длиной Это противоречит условию задачи, так как любая простая цепь графа не может превосходить длины Отсюда следует, что