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

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

Формально, хроматическое число — минимальное число $k$ , такое что множество $V$ вершин графа $G$ можно разбить на $k$ непересекающихся классов $C_{1},C_{2},\ldots ,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 '(G)$ . Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырёх красок. Рёберная раскраска определяет 1-факторизацию графа.

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

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

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

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

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

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

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