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

Пример раскраски графа Петерсена. Для раскраски этого графа достаточно 3 разных цвета, его хроматическое число равно 3.

Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).

Определение

Хроматическое число графа — минимальное число $k$, такое что множество $V$ вершин графа можно разбить на $k$ непересекающихся классов $C_{1},C_{2},\ldots ,C_{k}$:

$V=\bigcup _{i}^{}C_{i};\ C_{i}\cap C_{j}=\varnothing ,$

таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.

Связанные определения

• K-раскрашиваемый граф — граф, хроматическое число которого не превосходит $K$. То есть его вершины можно раскрасить не более чем $K$ цветами так, что у любого ребра концы будут разного цвета.
• K-хроматический граф — граф, хроматическое число которого равно $K$. То есть вершины графа можно раскрасить $K$ цветами так, что у любого ребра концы будут разного цвета, но так раскрасить $K-1$ цветами — уже нельзя.

Рёберная раскраска

Основная статья: Рёберная раскраска

реберная раскраска кубического графа

Хроматический класс графа G — минимальное число цветов, в которые можно раскрасить ребра графа G так, чтобы смежные ребра имели разные цвета. Обозначается χ'(G). Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырёх красок. Реберная раскраска определяет 1-факторизацию графа.

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

Если рассмотреть количество различных раскрасок помеченного графа как функцию от доступного числа цветов t, то оказывается, что эта функция всегда будет полиномом от t. Этот факт был обнаружен Биркгофом и Льюисом при попытке доказать проблему четырёх красок.

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

Треугольник $K_{3}$	$t(t-1)(t-2)$
Полный граф $K_{n}$	$t(t-1)(t-2)...(t-(n-1))$
Дерево с $n$ вершинами	$t(t-1)^{n-1}$
Цикл $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Граф Петерсена	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

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

Для графа-вершины хроматический многочлен равен $t$

$|V(G)|=1\Rightarrow P(G,t)=t.$

Хроматический многочлен графа равен произведению хроматических многочленов его компонент

$G_{1}\cap G_{2}=\emptyset \Rightarrow P((G_{1}\cup G_{2}),t)=P(G_{1},t)P(G_{2},t).$

Также существует рекуррентное соотношение — теорема Зыкова, так называемая формула удаления и стягивания

$P(G,t)=P(G-(u,v),t)-P(G/(u,v),t),$

где $u$ и $v$ — смежные вершины, $G-(u,v)$ — граф, получающийся из графа $G$ путём удаления ребра $(u,v),$ а $G/(u,v)$ — граф, получающийся из графа $G$ путём стягивания ребра $(u,v)$ в точку.
Можно использовать эквивалентную формулу

$P(G,t)=P(G+(u,v),t)+P(G/(u,v),t),$

где $u$ и $v$ — несмежные вершины, а $G+(u,v)$ — граф, получающийся из графа $G$ путём добавления ребра $(u,v).$

Свойства хроматического многочлена

Для всех целых положительных $t$

$P(G,t)\geq 0.$

Хроматическое число $\chi (G)$ — наименьшее целое положительное $t$, для которого

$P(G,t)>0.$

Степень хроматического многочлена равна количеству вершин:

$\deg P(G,t)=|V(G)|$

Обобщения

Также хроматическое число можно рассматривать для других объектов, например, для метрических пространств. Так, хроматическим числом плоскости называется минимальное число цветов χ, для которого существует такая раскраска всех точек плоскости в один из цветов, что никакие две точки одного цвета не находятся на расстоянии ровно 1 друг от друга. Аналогично для любой размерности пространства. Элементарно доказывается, что для плоскости $4\leqslant \chi \leqslant 7$, однако продвинуться дальше долгое время не удавалось. 8 апреля 2018 года, британский математик Обри ди Грей доказал, что $\chi >4$. Эта задача называется задачей Нелсона — Эрдёша — Хадвигера.

Значение для теории графов

Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырёх красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырёх красок, гипотеза Хадвигера.

См. также

• Практическое применение раскраски графов
• Сочетание

Примечания

Литература

• О. Оре. Теория графов. — М.: Наука, 1986.