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

Кёниг). Граф является -хроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Достаточность. Пусть в графе  нет циклов нечетной длины. Будем считать, что граф связный (в противном случае можно рассмотреть отдельно каждую компоненту связности).

Рис. 137.

Раскрашиваем его следующим образом: 1) произвольную вершину  окрасим цветом  если вершина  окрашена цветом  то все смежные с ней вершины окрасим цветом  а если  окрашена цветом  то все смежные с ней вершины окрасим цветом  Так как граф связный, то в конце концов все его вершины будут окрашены, причем никакая вершина не будет окрашена двумя разными цветами, так как в графе нет цйклов нечетной длины.

Необходимость. Если граф -хроматический, то он не содержит циклов нечетной длины, так как иначе вершины такого цикла нельзя раскрасить двумя цветами требуемым образом Теорема II.

Для того чтобы граф  был -хроматическим, необходимо и достаточно, чтобы существовал соответствующий ему симметрический граф  без петель, допускающий такую функцию Гранди  что

Условие достаточно. Если такая  существует, то каждому целому числу от 0 до  сопоставим некоторый цвет и окрасим вершину  в соответствии со значением 

Условие необходимо. Если граф -хроматический, то покажем, что существует функция Гранди, максимальное значение которой не превосходит  Пусть такие подмножества, что вершины каждого из них окрашены одинаково. Каждую вершину  не смежную ни с какой вершиной из  присоединяем к  и получаем  Затем каждую вершину  не смежную ни с какой вершиной из присоединяем к  и получаем  Аналогично получаем  Тогда функция равная  если  функция Гранди, удовлетворяющая (33.17).

Рис. 138.

Эта теорема показывает, что отыскание функции Гранди для симметрического графа без петель сводится к задаче о раскраске соответствующего неориентированного графа (любой раскраске отвечает функция Гранди) и, обратно, любой функции Гранди отвечает некоторая раскраска графа.

Например, для симметрического графа без петель на рис. 138, соответствующего неориентированному графу на рис. 136, исходя из раскраски, заданной на рис. 137, получаем функцию Гранди соответствием:  Можно действовать и в обратном порядке.

Теорема III. Пусть  хроматическое число графа  соответствующего графу без петель. Тогда число внутренней устойчивости  удовлетворяет неравенству

В самом деле,  можно разбить на  устойчивых множеств, каждое из которых образовано  вершинами одного цвета,  Тогда

Хроматический класс. Рассмотрим граф  и целое число  такое, что: 1) ребра графа можно окрасить  цветами

так, что смежные ребра не окрашиваются одинаково; 2) это невозможно осуществить  цветами.

Число  называют хроматическим классом графа 

Рис. 139.