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

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

Для полных графов требуется на единицу больше цветов, чем их максимальная степень. Эти графы и нечётные циклы являются единственными исключениями для теоремы Брукса.

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

Формулировка

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

Доказательство

Ласло Ловас (László Lovász 1975) даёт упрощённое доказательство теоремы Брукса. Если граф не является двусвязным, его двусвязные компоненты можно раскрасить по отдельности, а затем объединить раскраски. Если граф содержит вершину v со степенью, меньшей Δ, то алгоритм жадной раскраски, который раскрашивает вершины согласно расстоянию от v (дальние — в первую очередь, ближние — в последнюю), использует максимум Δ цветов. Таким образом, наиболее сложными случаями для доказательства являются двусвязные Δ-регулярные графы с Δ ≥ 3. Ловас показывает, что можно найти остовное дерево такое, что некоторые несмежные соседи u и w корня v являются листьями дерева. Присвоим вершинам u и w один (любой) цвет. Жадный алгоритм, начинающийся в u и w и проходящий остальные вершины остовного дерева (поднимаясь от корня к листьям), использует максимум Δ цветов. Когда все вершины, отличные от v, раскрашены, они имеют неокрашенного родителя, так что уже выкрашенные цвета не могут использовать все свободные цвета, поскольку два соседа v (u и w) имеют один цвет. В неиспользованный цвет раскрасим саму вершину v.

Обобщения

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

Для некоторых типов графов нужно даже меньше Δ цветов. Рид (Reed 1999) показал, что Δ − 1 цветов достаточно тогда и только тогда, когда граф не содержит Δ-клики, но при этом Δ должно быть достаточно большим. Для графов без треугольников, а также для более общего класса графов, в которых окрестности вершин достаточно разрежены, достаточно O(Δ/log Δ) цветов..

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

Алгоритмы

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

Ссылки

• Noga Alon, Michael Krivelevich, Benny Sudakov. Coloring graphs with sparse neighborhoods // Journal of Combinatorial Theory, Series B. — 1999. — Т. 77, вып. 1. — С. 73–82. — doi:10.1006/jctb.1999.1910.
• R. L. Brooks. On colouring the nodes of a network // Proc. Cambridge Philosophical Society, Math. Phys. Sci.. — 1941. — Т. 37. — С. 194–197. — doi:10.1017/S030500410002168X..
• Gary Chartrand, Ping Zhang. Chromatic graph theory. — Boca Raton, London, New York: CRC Press/Chapman & Hall, 2009. — С. 187. — (Discrete Mathematics and its applications)..

• David A. Grable, Alessandro Panconesi. Journal of Algorithms. SODA '98: Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. — Philadelphia, PA, USA: Society for Industrial and Applied Mathematics, 1998. — Т. 37. — С. 473–480. — doi:10.1006/jagm.2000.1097.
• Péter Hajnal, Endre Szemerédi. Brooks coloring in parallel // SIAM Journal on Discrete Mathematics. — 1990. — Т. 3, вып. 1. — С. 74–80. — doi:10.1137/0403008..
• H. J. Karloff. An NC algorithm for Brooks' theorem // Theoretical Computer Science. — 1989. — Т. 68, вып. 1. — С. 89–103. — doi:10.1016/0304-3975(89)90121-7..
• L. Lovász. Three short proofs in graph theory // Journal of Combinatorial Theory, Series B. — 1975. — Т. 19. — С. 269–271. — doi:10.1016/0095-8956(75)90089-1..
• Alessandro Panconesi, Aravind Srinivasan. The local nature of Δ-coloring and its algorithmic applications // Combinatorica. — 1995. — Т. 15, вып. 2. — С. 255–280. — doi:10.1007/BF01200759..
• Bruce Reed. A strengthening of Brooks' theorem // Journal of Combinatorial Theory, Series B. — 1999. — Т. 76, вып. 2. — С. 136–149. — doi:10.1006/jctb.1998.1891..
• San Skulrattanakulchai. Δ-List vertex coloring in linear time // Information Processing Letters. — 2006. — Т. 98, вып. 3. — С. 101–106. — doi:10.1016/j.ipl.2005.12.007..
• В.Г. Визинг. Методы дискретного анализа в теории кодов и схем: сборник научных трудов.. — Новосибирск: Институт математики СО АН СССР, 1976. — Т. 29. — С. 3–10..
• Weisstein, Eric W. Brooks' Theorem (англ.) на сайте Wolfram MathWorld.