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

Справедливая раскраска — это назначение цветов вершинам неориентированного графа таким образом, что

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

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

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

Примеры

Справедливая раскраска звезды K_1,5.

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

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

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

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

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

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

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

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

Для любого дерева с максимальной степенью $\Delta$, справедливое хроматическое число не превосходит

$1+\lceil \Delta /2\rceil$

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

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

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

Приложения

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

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

Ссылки

• ECOPT A Branch and Cut algorithm for solving the Equitable Coloring Problem