(Вершинной) \(k\)-раскраской графа \(G\) называется любая функция \(f \colon VG \to \{ 1, 2, \ldots, k \}\).
\(k\)-раскраска \(f\) называется правильной, если для любой пары смежных вершин \(u\) и \(v\) выполнено \(f(u) \neq f(v)\).
Граф называется \(k\)-раскрашиваемым, если для него существует правильная \(k\)-раскраска.
Хроматическим числом графа \(G\) называется минимальное натуральное \(k\), при котором граф \(G\) будет \(k\)-раскрашиваемым.
Обозначается это число \(\chi(G)\).
При этом граф \(G\) называется \(k\)-хроматическим. Для графа \(G\) с \(\chi(G) = k\) правильную \(k\)-раскраску называют минимальной или оптимальной.
Некоторые общие замечания: - для полного графа \(K_n\) с \(n\) вершинами \(\chi(K_n) = n\) - для любого двудольного графа \(G\) верно \(\chi(G) = 2\) - граф является 1-хроматическим т.т.т. он пустой - граф является 2-хроматическим т.т.т. он двудольный и непустой - когда в общем граф 3-хроматический неизвестно - если \(H\) — подграф графа \(G\) и \(\chi(H) = k\), то \(\chi(G) \geq k\) - если компоненты графа \(k\)-раскрашиваемы, то и граф тоже
Кроме того, раскраску можно свести очевидно к двусвязным графам.
Блоком или компонентой (вершинной) двусвязности графа называется максимальный по включению связный подграф, не имеющий точек сочленения.
Теорема. Если любой блок графа \(k\)-раскрашиваем, то и сам граф \(k\)-раскрашиваем.
Блок можно раскрасить отдельно от остального графа, а затем (если нужно) переставить цвета.
Задача составления расписаний
Предположим, что нужно провести несколько занятий за кратчайшее время. Каждое занятие длится один час, но не все занятия могут идти одновременно.
Построим граф \(G\), вершины которого соответствуют занятиям, и две вершины смежны, если соответствующие занятия нельзя вести одновременно.
Правильная раскраска определяет возможное расписание. Любое возможное расписание определяет правильную раскраску.
Минимальная раскраска дает оптимальное расписание. Все занятия можно провести не быстрее \(\chi(G)\) часов.
Теорема. Если наибольшая из степеней вершин графа не превышает \(d\), то этот граф \((d+1)\)-раскрашиваем.
Предположим, что графы с \(n\) вершинами удовлетворяют условию. Если удалить из графа с \(n+1\) вершинами одну, то его можно \((d+1)\)-раскрасить. Окружение удаленной вершины окрашено в не более чем \(d\) цветов, поэтому удаленную можно докрасить в \((d+1)\)-ый цвет.
Лемма. В любом плоском графе найдется вершина степени не превышающей 5.
По формуле Эйлера для плоского \((n,m)\)-графа число граней \(f\) удовлетворяет равенству \(2 = n - m + f\)
Кроме этого, \(3f \leq 2m\), так как - каждую грань ограничивает минимум 3 ребра и - каждое ребро либо разделяет две грани, либо является мостом
Получаем \(2 = n - m + f \leq n - m + \frac{2m}{3} = n - \frac{m}{3}\).
По лемме о рукопожатиях сумма всех степеней равна удвоенному числу ребер: \(2m = \sum d(v)\).
Подставляем, \(n - \frac{1}{6} \sum d(v) \geq 2\), \(6n - \sum d(v) \geq 12\) или \(\sum (6 - d(v)) \geq 12\). Значит все \(d(v)\) не могут быть больше 5.
Теорема. Любой планарный граф 5-раскрашиваем.
Утверждение верно для графов с 5 и менее вершинами.
Предположим, для всех графов с \(n\) вершинами все доказано. Пусть \(G\) - плоский граф с \(n+1\) вершиной.
По Лемме \(G\) содержит вершину \(v\) степени \(d(v) \leq 5\).
Если \(d(v) \leq 4\), то можно сначала раскрасить \(G - v\), а затем и \(v\) в оставшийся неиспользованным в ее окружении цвет.
Пусть \(d(v) = 5\). В окружении \(v\) есть несмежные вершины \(v_1\) и \(v_2\) (иначе это непланарный \(K_5\)).
Обозначим \(G'\) граф, полученный из \(G - v\) слиянием \(v_1\) и \(v_2\) в вершину \(u\). Граф \(G'\) можно 5-раскрасить.
В исходном \(G\) используем раскраску \(G'\), \(v_1\) и \(v_2\) красим в цвет \(u\), а вершину \(v\) раскрашиваем в оставшийся цвет.
Теорема. (Аппель-Хакен, 1976) Любой планарный граф 4-раскрашиваем.
Алгоритм последовательной раскраски: произвольно взятую вершину красим в минимальный цвет, не использованный при раскраске ее окружения.
Хроматической функцией графа \(G\) называется функция \(f(t)\), ставящая всякому натуральному числу \(t\) количество правильных \(t\)-раскрасок графа \(G\).
Хроматическая функция полного графа \(K_n\) есть \(f(t) = t (t-1) \ldots (t - (n-1))\) если \(t \geq n\) и \(f(t) = 0\) если \(t < n\).
Теорема. Граф \(G\) является деревом порядка \(n\) тогда и только тогда, когда его хроматическая функция \(f(t) = t (t-1)^{n-1}\).
Лемма. Пусть \(u\) и \(v\) - две несмежные вершины графа \(G\). Если \(G_1 = G + uv\) и \(G_2\) получается из \(G\) слиянием вершин \(u\) и \(v\), то верно равнество хроматических функций \(f(G, t) = f(G_1, t) + f(G_2, t)\).
Число правильных \(t\) раскрасок \(G\) равно числу раскрасок, в которых \(u\) и \(v\) раскрашены по разному (оно равно \(f(G_1, t)\)), плюс число раскрасок, в которых \(u\) и \(v\) раскрашены одинаково (равно \(f(G_2, t)\)).
Теорема. Хроматическая функция графа является многочленом от \(t\).
Вычисление сводится к вычислению функций полных графов.