Теорема Брукса - Brooks theorem - Wikipedia

Полные графики нужно на один цвет больше, чем их максимальная степень. Они и нечетные циклы - единственные исключения из теоремы Брукса.

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

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

Официальное заявление

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

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

Ласло Ловас  (1975 ) дает упрощенное доказательство теоремы Брукса. Если график не двусвязный, его двусвязные компоненты могут быть окрашены отдельно, а затем окраски объединены. Если у графа есть вершина v степени меньше Δ, то a жадная окраска алгоритм, который окрашивает вершины дальше от v прежде, чем более близкие будут использовать не более Δ цветов. Поэтому наиболее сложный случай доказательства касается двусвязных Δ-обычный графов с Δ ≥ 3. В этом случае Ловас показывает, что можно найти остовное дерево такие, что два несмежных соседа ты и ш корня v листья на дереве. Жадная окраска начиная с ты и ш и обработка оставшихся вершин остовного дерева в порядке снизу вверх, заканчиваясь на v, использует не более Δ цветов. Ведь когда каждая вершина, кроме v окрашен, у него есть неокрашенный родитель, поэтому его уже окрашенные соседи не могут использовать все свободные цвета, а в v два соседа ты и ш иметь одинаковые цвета, поэтому снова остается свободный цвет для v сам.

Расширения

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

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

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

Алгоритмы

Δ-раскраска или даже Δ-раскраска графа степени Δ может быть найдена за линейное время.[2] Известны также эффективные алгоритмы для поиска раскрасок Брукса в параллельных и распределенных моделях вычислений.[3]

Примечания

  1. ^ Алон, Кривелевич и Судаков (1999).
  2. ^ Скулраттанакулчай (2006).
  3. ^ Карлофф (1989); Хайнал и Семереди (1990); Панконези и Шринивасан (1995); Грейбл и Панконези (2000).

Рекомендации

  • Алон, Нога; Кривелевич Михаил; Судаков, Бенни (1999), «Раскраска графов с разреженными окрестностями», Журнал комбинаторной теории, Серия B, 77 (1): 73–82, Дои:10.1006 / jctb.1999.1910
  • Брукс, Р.Л. (1941), «О окраске узлов сети», Математические труды Кембриджского философского общества, 37 (2): 194–197, Дои:10.1017 / S030500410002168X.
  • Грейбл, Дэвид А .; Панконези, Алессандро (2000), "Быстрые распределенные алгоритмы для раскраски Брукса – Визинга", Журнал алгоритмов, 37: 85–120, Дои:10.1006 / jagm.2000.1097.
  • Хайнал, Петер; Семереди, Эндре (1990), «Раскраски ручьев параллельно», Журнал SIAM по дискретной математике, 3 (1): 74–80, Дои:10.1137/0403008.
  • Карлофф, Х. Дж. (1989), "Алгоритм NC для теоремы Брукса", Теоретическая информатика, 68 (1): 89–103, Дои:10.1016/0304-3975(89)90121-7.
  • Ловас, Л. (1975), «Три коротких доказательства в теории графов», Журнал комбинаторной теории, Серия B, 19 (3): 269–271, Дои:10.1016/0095-8956(75)90089-1.
  • Панконези, Алессандро; Сринивасан, Аравинд (1995), "Локальный характер Δ-раскраски и ее алгоритмические приложения", Комбинаторика, 15 (2): 255–280, Дои:10.1007 / BF01200759.
  • Рид, Брюс (1999), "Усиление теоремы Брукса", Журнал комбинаторной теории, Серия B, 76 (2): 136–149, Дои:10.1006 / jctb.1998.1891.
  • Скулраттанакулчай, Сан (2006), «Раскраска вершин Δ-списка за линейное время», Письма об обработке информации, 98 (3): 101–106, Дои:10.1016 / j.ipl.2005.12.007.
  • Визинг, В. Г. (1976), "Раскраски вершин заданными цветами", Дискрет. Анализ. (на русском), 29: 3–10.

внешняя ссылка