Наименьшее возможное число
компонент в разложении (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) все компоненты С, являются независимыми. Из определения числа
следует, что