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

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

Хромати́ческое число́ гра́фа ${\boldsymbol {G}}$ — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается $\chi (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$ цветами — уже нельзя.

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

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

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

Хроматический класс графа ${\boldsymbol {G}}$ — минимальное число цветов, в которые можно раскрасить ребра графа $G$ так, чтобы смежные ребра имели разные цвета. Обозначается $\chi '(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)|$

Обобщения

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

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

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

См. также

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

Литература

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