Теорема Брукса

Теорема Брукса — утверждение в теории графов, устанавливающее связь между максимальной степенью графа и его хроматическим числом. Согласно этой теореме вершины связного графа, в котором все вершины имеют не больше  соседей, можно раскрасить всего в  цветов, за исключением двух случаев — полных графов и циклов нечётной длины, для которых требуется  цветов.

Теорема носит имя , опубликовавшего доказательство теоремы в 1941 году. Раскраска с использованием числа цветов, указанной в теореме Брукса иногда называется раскраской Брукса, или -раскраской.

Формулировка 
Для связного неориентированного графа  с максимальной степенью  хроматическое число графа  не больше , за исключением случаев, когда  — клика или нечётный цикл. В этих случаях хроматическое число равно .

Доказательство 
Ласло Ловас  даёт упрощённое доказательство теоремы Брукса.
Если граф не является двусвязным, его двусвязные компоненты можно раскрасить по отдельности, а затем объединить раскраски.
Если граф содержит вершину  со степенью, меньшей , то алгоритм жадной раскраски, который раскрашивает вершины согласно расстоянию от  (дальние — в первую очередь, ближние — в последнюю), использует максимум  цветов. Таким образом, наиболее сложными случаями для доказательства являются двусвязные -регулярные графы с . Ловас показывает, что можно найти остовное дерево такое, что некоторые несмежные соседи  и  корня  являются листьями дерева. Присвоим вершинам  и  один (любой) цвет.
Жадный алгоритм, начинающийся в  и  и проходящий остальные вершины остовного дерева (поднимаясь от корня к листьям), использует максимум  цветов. Когда все вершины, отличные от , раскрашены, они имеют неокрашенного родителя, так что уже выкрашенные цвета не могут использовать все свободные цвета, поскольку два соседа  ( и ) имеют один цвет. В неиспользованный цвет раскрасим саму вершину .

Обобщения 
Более общая версия теоремы относится к предписанной раскраске — если задан связный неориентированный граф с максимальной степенью , не являющийся ни кликой, ни циклом нечётной длины, и список  цветов для каждой вершины, можно выбрать цвет каждой вершины из списка так, что никакие две смежные вершины не имеют один цвет. Другими словами, предписанное хроматическое число связного неориентированного графа никогда не превосходит , если только G не является кликой или циклом нечётной длины. Теорема была доказана Визингом .

Для некоторых типов графов нужно даже меньше  цветов. Рид  показал, что  цветов достаточно тогда и только тогда, когда граф не содержит -клики, но при этом  должно быть достаточно большим. Для графов без треугольников, а также для более общего класса графов, в которых окрестности вершин достаточно разрежены, достаточно  цветов..

Степень графов появляется также при оценке верхней границы другого типа окраски — рёберной. Теорема Визинга утверждает, что хроматический индекс не превосходит . Расширение теоремы Брукса на тотальную раскраску, утверждающее, что тотальное хроматическое число не превосходит , было предложено Бехзадом и Визингом в качестве гипотезы. Теорема Хайналя — Семереди о равномерной раскраске утверждает, что любой граф имеет -цветную раскраску, при которой число вершин двух различных цветов отличается максимум на единицу.

Алгоритмы 
-раскраску, или даже предписанную -раскраску, графа со степенью  можно найти за линейное время.
Известны эффективные алгоритмы для поиска раскраски Брукса в параллельных и распределённых средах вычислений .

Примечания

Ссылки 
 
 .
 .

 
 .
 .
 .
 .
 .
 .
 .
 
Б
Раскраска графа