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

У теорії графів, теорема Брукса встановлює зв'язок між максимальним степенем графа і його хроматичним числом. Згідно з теоремою, зв'язний граф, у якому кожна вершина має не більше Δ сусідів, вершини можуть бути пофарбовані не більше ніж в Δ кольорів, за винятком двох випадків — повний граф і граф-цикл непарної довжини, які вимагають Δ + 1 кольорів.

Повні графи потребують на один колір більше, ніж їх максимальний степінь. Вони та непарні цикли є єдиними винятками з теореми Брукса.

Теорема названа на честь ^[en], який опублікував доказ в 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.

Узагальнення

Більш загальна версія теореми відноситься до ^[en] — якщо заданий зв'язний неорієнтований граф з максимальним степенем Δ, який не є ні клікою, ні циклом непарної довжини, і список Δ кольорів для кожної вершини, можна вибрати колір кожної вершини зі списку так, що ніякі дві суміжні вершини не мають один колір. Іншими словами, запропоноване хроматичне число зв'язкового неорієнтованого графа ніколи не перевершує Δ, якщо лише G не є клікою або циклом непарної довжини. Теорема була доведена Вадимом Візінгом.

Для деяких типів графів потрібно навіть менше Δ кольорів. ^[en](1999) показав, що Δ-1 кольорів достатньо тоді і лише тоді, коли граф не містить Δ-кліки, але при цьому Δ має бути достатньо великим. Для графів без трикутників, а також для більш загального класу графів, в яких околи вершин достатньо розріджені, достатньо O(Δ/log Δ) кольорів.

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

Алгоритми

Δ-розмальовку, або навіть приписану Δ-розмальовку, графа зі ступенем Δ можна знайти за лінійний час. Відомі ефективні алгоритми для пошуку розмальовки Брукса в паралельних і розподілених середовищах обчислень.

Примітки

1. Chartrand, Zhang, 2009 та Теорема 7.15 (Brooks’ Theorem), стр. 186.
2. Chartrand, Zhang, 2009 та Теорема 7.10, стор. 182.
3. (Alon, Krivalevich, Sudakov, 1999).
4. Skulrattanakulchai, 2006
5. Karloff, 1989; Hajnal, Szemerédi, 1990; Panconesi, Srinivasan, 1995; Grable, Panconesi, 1998

Посилання

• 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. — CRC Press/Chapman & Hall. — Boca Raton, London, New York, 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. — Society for Industrial and Applied Mathematics. — Philadelphia, PA, USA, 1998. — Т. 37. — С. 473–480. — DOI:10.1006/jagm.2000.1097..
• Péter Hajnal. 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. 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.