В теории графов теорема Брукса устанавливает связь между максимальной степенью графа и его хроматическим числом . Согласно теореме, в связном графе, в котором каждая вершина имеет не более Δ соседей, вершины могут быть раскрашены только Δ цветами, за исключением двух случаев: полных графов и циклических графов нечетной длины, для которых требуется Δ + 1 цвет.
Теорема названа в честь Р. Леонарда Брукса , который опубликовал ее доказательство в 1941 году. [1] Раскраску с числом цветов, описанным теоремой Брукса, иногда называют раскраской Брукса [2] или Δ- раскраской . [3]
Для любого связного неориентированного графа G с максимальной степенью Δ хроматическое число графа G не превышает Δ, если только G не является полным графом или нечетным циклом, в этом случае хроматическое число равно Δ + 1. [1]
Ласло Ловас дает упрощенное доказательство теоремы Брукса. Если граф не является двусвязным , его двусвязные компоненты можно раскрасить отдельно, а затем объединить раскраски. Если граф имеет вершину v со степенью меньше Δ, то жадный алгоритм раскраски , который раскрашивает вершины, более удаленные от v, прежде чем более близкие, использует не более Δ цветов. Это происходит потому, что в то время, когда каждая вершина, отличная от v , раскрашивается, по крайней мере один из ее соседей (тот, что находится на кратчайшем пути к v ) не раскрашен, поэтому у него меньше Δ раскрашенных соседей и есть свободный цвет. Когда алгоритм достигает v , его небольшое количество соседей позволяет раскрасить его. Таким образом, самый сложный случай доказательства касается двусвязных Δ- регулярных графов с Δ ≥ 3. В этом случае Ловас показывает, что можно найти остовное дерево, такое, что два несмежных соседа u и w корня v являются листьями в дереве. Жадная раскраска, начинающаяся с u и w и обрабатывающая оставшиеся вершины остованого дерева снизу вверх, заканчивающаяся в v , использует не более Δ цветов. Ведь когда каждая вершина, отличная от v , окрашена, у нее есть неокрашенный родитель, поэтому ее уже окрашенные соседи не могут использовать все свободные цвета, в то время как в v два соседа u и w имеют одинаковые цвета, поэтому снова остается свободный цвет для самой v . [4]
Более общая версия теоремы применима к списковому раскрашиванию : если задан любой связный неориентированный граф с максимальной степенью Δ, который не является ни кликой , ни нечетным циклом, и список цветов Δ для каждой вершины, можно выбрать цвет для каждой вершины из ее списка так, чтобы никакие две смежные вершины не имели одинаковый цвет. Другими словами, списковое хроматическое число связного неориентированного графа G никогда не превышает Δ, если только G не является кликой или нечетным циклом. [5]
Для некоторых графов может потребоваться даже меньше Δ цветов. Δ − 1 цветов достаточно тогда и только тогда, когда данный граф не имеет Δ-клики, при условии, что Δ достаточно велико. [6] Для графов без треугольников или, в более общем случае, графов, в которых окрестность каждой вершины достаточно разрежена , достаточно O(Δ/log Δ) цветов. [7]
Степень графа также появляется в верхних границах для других типов раскраски; для раскраски рёбер результат, что хроматический индекс не превышает Δ + 1, является теоремой Визинга . Расширение теоремы Брукса на полную раскраску , утверждающее, что полное хроматическое число не превышает Δ + 2, было выдвинуто Мехди Бехзадом и Визингом. Теорема Хайнала–Семереди о справедливой раскраске утверждает, что любой граф имеет (Δ + 1)-раскраску, в которой размеры любых двух цветовых классов отличаются не более чем на единицу.
Δ-раскраска или даже Δ-раскраска списка степени Δ может быть найдена за линейное время. [8] Также известны эффективные алгоритмы для поиска раскрасок Брукса в параллельных и распределенных моделях вычислений. [9]