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

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

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

То есть, разбиение вершин на различные цвета настолько однородно, насколько это возможно. Например, задание каждой вершине различных цветов было бы равномерной раскраской, но, как правило, при этом будет использовано намного больше цветов, чем необходимо для оптимальной равномерной раскраски. Эквивалентный способ определения равномерной раскраски — это вложение заданного графа в качестве подграфа в граф Турана с тем же множеством вершин. Есть два вида хроматических чисел, ассоциированных с равномерной раскраской. Равномерное хроматическое число графа 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$ других, равномерная раскраска графа зависимости может быть использована для разбиения переменных на независимые подмножества внутри которых можно вычислить границы Чернова, что даст более точные границы для дисперсии, чем при разбиении неравномерным способом.

Литература

• Henry A. Kierstead, Alexandr V. Kostochka, Marcelo Mydlarz, Endre Szemerédi. A fast algorithm for equitable coloring // Combinatorica. — 2010. — Т. 30, вып. 2. — ISSN 0209-9683. — doi:10.1007/s00493-010-2483-5.
• Hans L. Bodlaender, Fedor V. Fomin. Equitable colorings of bounded treewidth graphs // Theoretical Computer Science. — 2005. — Т. 349, вып. 1. — С. 22–30. — doi:10.1016/j.tcs.2005.09.027.
• Bollobás B., Eldridge S. E. Packings of graphs and applications to computational complexity // Journal of Combinatorial Theory. — 1978. — Т. 25, вып. 2. — С. 105–124. — doi:10.1016/0097-3165(78)90073-0.
• Béla Bollobás, Richard K. Guy. Equitable and proportional coloring of trees // Journal of Combinatorial Theory. — 1983. — Т. 34, вып. 2. — С. 177–186. — doi:10.1016/0095-8956(83)90017-5.
• Paul A. Catlin. Subgraphs of graphs. I. // Discrete Math.. — 1974. — Т. 10, вып. 2. — С. 225–233. — doi:10.1016/0012-365X(74)90119-8.
• Bor-Liang Chen, Ko-Wei Lih. Equitable coloring of trees // Journal of Combinatorial Theory. — 1994. — Т. 61, вып. 1. — С. 83–87. — doi:10.1006/jctb.1994.1032.
• Bor-Liang Chen, Ming-Tat Ko, Ko-Wei Lih. Equitable and m-bounded coloring of split graphs // Combinatorics and Computer Science (Brest, 1995). — Berlin: Springer-Verlag, 1996. — Т. 1120. — С. 1–5. — (Lecture Notes in Computer Science). — ISBN 978-3-540-61576-7. — doi:10.1007/3-540-61576-8_67.
• Corrádi K., András Hajnal. On the maximal number of independent circuits in a graph // Acta Mathematica Academiae Scientiarum Hungaricae. — 1963. — Т. 14, вып. 3–4. — С. 423–439. — doi:10.1007/BF01895727.
• Paul Erdős. Problem 9 // Theory of Graphs and its Applications / Fieldler M.. — Prague: Czech Acad. Sci. Publ., 1964. — С. 159.
• Michael Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances Rosamond, Saket Saurabh, Stefan Szeider, Carsten Thomassen. On the complexity of some colorful problems parameterized by treewidth // Combinatorial optimization and applications. — Berlin: Springer-Verlag, 2007. — Т. 4616. — С. 366–377. — (Lecture Notes in Computer Science). — ISBN 978-3-540-73555-7. — doi:10.1007/978-3-540-73556-4_38.
• Hanna Furmańczyk. Equitable coloring of graph products // Opuscula Mathematica. — 2006. — Т. 26, вып. 1. — С. 31–44.
• András Hajnal, Endre Szemerédi. Proof of a conjecture of P. Erdős // Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969). — North-Holland, 1970. — С. 601–623.
• Svante Janson, Andrzej Ruciński. The infamous upper tail // Random Structures &Algorithms. — 2002. — Т. 20, вып. 3. — С. 317–342. — doi:10.1002/rsa.10031.
• Kierstead H. A., Kostochka A. V. A short proof of the Hajnal-Szemerédi theorem on equitable colouring // Combinatorics, Probability and Computing. — 2008. — Т. 17, вып. 2. — С. 265–270. — doi:10.1017/S0963548307008619.
• János Komlós, Gábor N. Sárközy, Endre Szemerédi. Proof of the Seymour conjecture for large graphs // Annals of Combinatorics. — 1998. — Т. 2, вып. 1. — С. 43–60. — doi:10.1007/BF01626028.
• Walter Meyer. Equitable coloring // American Mathematical Monthly. — 1973. — Т. 80, вып. 8. — С. 920–922. — doi:10.2307/2319405. — .
• Sriram V. Pemmaraju. Equitable colorings extend Chernoff-Hoeffding bounds // Proc. 12th ACM-SIAM Symp. Discrete Algorithms (SODA 2001). — 2001. — С. 924–925. — (Soda '01). — ISBN 9780898714906.
• Paul Seymour. Problem section // Combinatorics: Proceedings of the British Combinatorial Conference 1973 / McDonough T. P., Mavron V. C.. — Cambridge, UK: Cambridge Univ. Press, 1974. — С. 201–202.

Ссылки

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