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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle P(G,t)=P(G-(u,v),t)-P(G/(u,v),t),}$

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

${\displaystyle P(G,t)=P(G+(u,v),t)+P(G/(u,v),t),}$

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

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

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

${\displaystyle P(G,t)\geq 0.}$

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

${\displaystyle P(G,t)>0.}$

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

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

Обобщения

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

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

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

См. также

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

Примечания

Литература

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