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

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

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

Формально, хроматическое число — минимальное число $k$, такое что множество $V$ вершин графа $G$ можно разбить на $k$ непересекающихся классов $C_1,C_2,\dots ,C_k$:

$V=\bigcup _i^{}{C}_i;C_i\cap C_j=\varnothing$

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

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

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

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

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

Хроматический класс графа $G$ — минимальное число цветов, в которые можно раскрасить ребра графа $G$ так, чтобы смежные ребра имели разные цвета. Обозначается ${\chi }^{\prime }(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=\mathrm{\varnothing }\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)⩾0$. Хроматическое число $\chi (G)$ — наименьшее целое положительное $t$, для которого $P(G,t)>0$. Степень хроматического многочлена равна количеству вершин — $\mathrm{deg}P(G,t)=|V(G)|$.

Обобщения

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

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

Литература

• Шаблон:Книга