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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Треугольник ${\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).}$

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

${\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)\geqslant 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}$^[3][4]. Эта задача называется задачей Нелсона — Эрдёша — Хадвигера.

Кроме того, множество вершин ${\displaystyle V}$ произвольного графа ${\displaystyle G}$ может быть рассмотрено как метрическое пространство, в котором расстояния между смежными вершинами равны ${\displaystyle b}$, а все остальные ненулевые расстояния равны ${\displaystyle a}$, где ${\displaystyle a<b\leqslant 2a}$ — произвольные фиксированные вещественные числа. ${\displaystyle a\Delta _{m}}$ — метрическое пространство, состоящее из ${\displaystyle m}$ точек, удалённых друг от друга на расстояние ${\displaystyle a}$. В этом случае имеет место следующий результат (Иванов — Тужилин, 2019^[5]): если ${\displaystyle m}$ — наибольшее натуральное число, для которого ${\displaystyle d_{GH}(V,a\Delta _{m})=b}$ (${\displaystyle d_{GH}(X,Y)}$ — расстояние Громова — Хаусдорфа между ${\displaystyle X}$ и ${\displaystyle Y}$; если таких натуральных чисел не существует, то считается ${\displaystyle m=0}$), то ${\displaystyle \chi (G)=m+1}$. Хроматическое число ${\displaystyle \chi (G)}$ равно ${\displaystyle 1}$, если и только если граф ${\displaystyle G}$ не содержит ни одного ребра. В этом случае равенство ${\displaystyle d_{GH}(V,a\Delta _{m})=b}$ не выполняется ни для какого ${\displaystyle m}$, поэтому, в силу сделанного соглашения, ${\displaystyle m=0}$, что приводит к верному равенству ${\displaystyle \chi (G)=0+1=1}$. По определению ${\displaystyle \chi (G)}$ не превосходит количества ${\displaystyle n}$ элементов множества ${\displaystyle V}$. С другой стороны, несложно показать, что ${\displaystyle d_{GH}(V,a\Delta _{p})\leq \max\{a,\,b-a\}<b}$ при каждом ${\displaystyle p\geqslant n}$, поэтому ${\displaystyle m<n}$ и, значит, ${\displaystyle \chi (G)=m+1\leqslant n}$.