Равномерная раскраска

Равномерная раскраска — это назначение цветов вершинам неориентированного графа таким образом, что:

Никакие две смежные вершины не имеют тот же самый цвет;
Число вершин в любых двух классах цветов отличаются не более чем на единицу.

То есть, разбиение вершин на различные цвета настолько однородно, насколько это возможно. Например, задание каждой вершине различных цветов было бы равномерной раскраской, но, как правило, при этом будет использовано намного больше цветов, чем необходимо для оптимальной равномерной раскраски. Эквивалентный способ определения равномерной раскраски — это вложение заданного графа в качестве подграфа в граф Турана с тем же множеством вершин. Есть два вида хроматических чисел, ассоциированных с равномерной раскраской. Равномерное хроматическое число графа G — это наименьшее число k, такое что граф G имеет равномерную раскраску с k цветами. Однако граф G может не иметь равномерные раскраски для некоторых больших наборов цветов. Равномерный хроматический порог графа G — это наименьшее число k, такое что граф G имеет равномерные раскраски для любого числа цветов, большего или равного k.

Теорема Хайнала — Семереди, которую сформулировал как гипотезу Пал Эрдёш, а доказали Андраш Хайнал и Эндре Семереди, утверждает, что любой граф с максимальной степенью Δ {displaystyle Delta } имеет равномерную раскраску с Δ + 1 {displaystyle Delta +1} цветами. Несколько связанных гипотез остаются открытыми. Известны также алгоритмы полиномиального времени для поиска раскраски, соответствующей этой границе, а также алгоритмы поиска оптимальных раскрасок специальных классов графов, но более общая задача определения, имеет ли произвольный граф равномерную раскраску с заданным числом цветов NP-полна.

Примеры

Звезда K1,5, показанная на рисунке, является полным двудольным графом, а поэтому может быть раскрашена двумя цветами. Однако получающаяся раскраска имеет одну вершину одного цвета и пять вершина другого цвета, а потому раскраска не является равномерной. Наименьшее число цветов в равномерной раскраске этого графа равна четырём, как показано на рисунке — центральная вершина должна принадлежать классу с единственной вершиной, так что остальные пять вершин должны быть разбиты по меньшей мере на три цвета, чтобы каждый класс содержал не более двух вершин. Более обще, Мейер заметил, что любая звезда K1,n требует 1 + ⌈ n / 2 ⌉ {displaystyle scriptstyle 1+lceil n/2 ceil } цветов для равномерной раскраски, а потому хроматическое число графа может отличаться от его хроматического равномерного числа не более чем в n/4 раз. Поскольку K1,5 имеет максимальную степень пять, число цветов, гарантированных по теореме Хайнала — Семереди, равно шести, что получается путём назначения каждой вершине различного цвета.

Другой интересный феномен показывает другой полный двудольный граф, K 2 n + 1 , 2 n + 1 {displaystyle K_{2n+1,2n+1}} . Этот граф имеет равномерную 2-раскраску, определённую его двудольностью. Однако он не имеет равномерной (2n + 1)-раскраски — любое равномерное разбиение вершин на это число цветов должно было бы иметь ровно две вершины на цвет, но две доли двудольного графа не могут быть разбиты на пары, поскольку содержат нечётное число вершин. Поэтому равномерный хроматический порог этого графа равно 2 n + 2 {displaystyle 2n+2} , что существенно больше его равномерного хроматического числа, равного двум.

Теорема Хайнала — Семереди

Теорема Брукса утверждает, что любой связный граф с максимальной степенью Δ {displaystyle Delta } имеет Δ {displaystyle Delta } -раскраску за двумя исключениями (полные графы и нечётные циклы). Однако эта раскраска может быть в общем случае далёкой от равномерной. Пал Эрдёш высказал гипотезу, что равномерная раскраска возможна всего с одним дополнительным цветом — любой граф с максимальной степенью Δ {displaystyle Delta } имеет равномерную раскраску с Δ + 1 {displaystyle Delta +1} цветами. Случай Δ = 2 {displaystyle Delta =2} не вызывает затруднений (любое объединение путей и циклов может быть равномерно раскрашено с помощью повторяющихся шаблонов с тремя цветами при небольших поправках для замкнутых циклов). Случай Δ + 1 = n / 3 {displaystyle Delta +1=n/3} решили Корради и Хайнал. Полную гипотезу доказали Хайнал и Семереди и она известна теперь как теорема Хайнала — Семереди. Их исходное доказательство было длинно и сложно. Более простое доказательство дали Кирстед и Косточка. Алгоритм полиномиального времени для поиска равномерных раскрасок с этим числом цветов описали Кирстед и Косточка. Они приписывают Марсело Мидларцу и Эндре Семереди другой, разработанный ранее, неопубликованный алгоритм полиномиального времени. Кирстед и Косточка также объявили об усиленной версии теоремы, что равномерная k-раскраска существует, если степени любых двух смежных вершин в сумме дают не более 2 k + 1 {displaystyle 2k+1} , однако доказательство так и не было опубликовано.

Мейер высказал гипотезу в виде теоремы Брукса для равномерной раскраски — любой связный граф с максимальной степенью Δ {displaystyle Delta } имеет равномерную раскраску с Δ {displaystyle Delta } или меньшим числом цветов, за исключением полных графов и нечётных циклов. Усиленная версия гипотезы утверждает, что каждый такой граф имеет равномерную раскраску с ровно Δ {displaystyle Delta } цветами, за исключением дополнительного исключения, полного двудольного графа, в котором обе доли имеют одно и тоже нечётное число вершин.

Сеймур предложил усиление теоремы Хайнала — Семереди, которое также включает теорему Дирака, что плотные графы Гамильтоновы — он высказал гипотезу, что если любая вершина в графе с n вершинами имеет по меньшей мере k n / ( k + 1 ) {displaystyle kn/(k+1)} соседей, то граф содержит в качестве подграфа граф, образованный путём соединения вершин, которые не более чем в k шагах в n-цикле. Случай k = 1 является самой теоремой Дирака. Теорема Хайнала — Семереди может быть перекрыта этой гипотезой путём применения гипотезы для больших значений k к дополнению графа и использования в качестве классов цветов непрерывные последовательности вершин из n-цикла. Гипотеза Сеймура доказана для графов, в которых n достаточно большое по сравнению с k. Доказательство использует некоторые глубокие средства, включая саму теорему Хайнала — Семереди.

Ещё одно обобщение теоремы Хайнала — Семереди — гипотеза Боллобаша — Элдриджа — Катлина (или, для краткости, БЭК-гипотеза). Оно утверждает, что если G1 и G2 являются графами с n вершинами с максимальной степенью Δ 1 {displaystyle Delta _{1}} и Δ 2 {displaystyle Delta _{2}} соответственно, и если ( Δ 1 + 1 ) ( Δ 2 + 1 ) ⩽ n + 1 {displaystyle (Delta _{1}+1)(Delta _{2}+1)leqslant n+1} , то G1 и G2 можно упаковать. То есть, G1 и G2 могут быть представлены на том же множестве из n вершин без общих рёбер. Теорема Хайнала — Семереди является специальным случаем гипотезы, в котором G2 является объединением непересекающихся клик. Катлин даёт похожее, но более сильное условие на Δ 1 {displaystyle Delta _{1}} и Δ 2 {displaystyle Delta _{2}} , при которых такая упаковка гарантированно существует.

Специальные случаи графов

Для любого дерева с максимальной степенью Δ {displaystyle Delta } равномерное хроматическое число не превосходит

1 + ⌈ Δ / 2 ⌉ {displaystyle 1+lceil Delta /2 ceil }

с худшим случаем на звезде. Однако большинство деревьев имеет существенно меньшее равномерное хроматическое число — если дерево с n вершинами имеет Δ ⩽ n / 3 − O ( 1 ) {displaystyle Delta leqslant n/3-O(1)} , то оно имеет равномерную раскраску с всего тремя цветами. Фурманчик изучал равномерное хроматическое число произведений графов.

Вычислительная сложность

Изучалась также задача поиска равномерных раскрасок с как можно меньшим числом цветов (ниже границы Хайнала — Семереди). Прямое сведение из раскраски графа к равномерной раскраске может быть доказано путём добавления в граф достаточного числа изолированных вершин, что показывает, что проверка, имеет ли граф равномерную раскраску с заданным числом цветов (большим двух), NP-полна. Однако задача становится более интересной, когда ограничена специальным классом графов или с точки зрения параметризованной сложности. Бодландер и Фомин показали, что если дан граф G и число цветов c, можно проверить, позволяет ли G равномерную c-раскраску за время O(nO(t)), где t — древесная ширина графа G. В частности, равномерная раскраска может быть решена оптимально за полиномиальное время для деревьев (что известно благодаря Чену и Ли) и внешнепланарных графов. Известен также алгоритм полиномиального времени для равномерной раскраски расщепляемых графов. Однако Феллоуз, Фомин, Локштанов и др. доказали, что когда древесная ширина является параметром алгоритма, задача W[1]-трудна. Таким образом маловероятно, что существует алгоритм полиномиального времени, независимый от этого параметра, или даже что зависимость от параметра может быть вынесена за скобки экспоненты в формуле времени работы.

Приложения

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

Теорема Хайнала — Семереди использовалась также для ограничения дисперсии сумм случайных переменных с ограниченной зависимостью. Если (как в условии локальной леммы Ловаса) каждая переменная зависит от максимум Δ {displaystyle Delta } других, равномерная раскраска графа зависимости может быть использована для разбиения переменных на независимые подмножества внутри которых можно вычислить границы Чернова, что даст более точные границы для дисперсии, чем при разбиении неравномерным способом.