Рёберная раскраска

Рёберная 3-цветная раскраска графа Дезарга.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $k$ различных цветов для заданного значения $k$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

По теореме Визинга число цветов, необходимых для рёберной раскраски простого графа, либо равно максимальной степени вершин $\Delta$, либо $\Delta +1$. Для некоторых графов, таких как двудольные графы и планарные графы высокой степени, число цветов всегда равно $\Delta$, а для мультиграфов число цветов может быть вплоть до $3{\Delta }/2$. Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов ${\Delta }+1$. Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время. Изучались много вариантов задачи рёберной раскраски, в которых условия назначения цвета ребру должны удовлетворять другим условиям, а не сопряжённости. Задачи рёберной раскраски имеют приложения в задачах расписания и в назначении частоты в оптоволоконных сетях.

Примеры

Граф-цикл может быть раскрашен в 2 цвета если длина цикла чётна — просто используем поочерёдно 2 цвета последовательно проходя рёбра цикла. Однако в случае нечётной длины потребуется 3 цвета.

Геометрическое построение раскраски полного графа $K_{8}$ в 7 цветов. Каждому из семи классов цветов принадлежит одно ребро, соединяющее центр и одну из вершин многоугольника, и три ребра, перпендикулярные ему.

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

Некоторые авторы изучали рёберную раскраску нечётных графов, $n$-регулярных графов, в которых вершины представляют команды из $(n-1)$ игроков из общего числа $2n-1$ игроков, и в которых рёбра представляют возможные пары этих команд (с одним игроком «вне игры» для судейства). В случае, когда $n=3$ получаем хорошо известный граф Петерсена. Как объясняет Биггс, задача (для $n=6$) состоит в том, что игроки хотят найти такое расписание, что команды играют каждую из шести игр в разные дни недели, исключая воскресенье для всех игроков. В математической формулировке они хотят найти 6-цветную рёберную раскраску 6-регулярных графов $O_{6}$. Когда $n$ равно 3, 4 или 8, рёберная раскраска графа $O_{n}$ требует $n+1$ цветов, но для 5, 6 и 7 нужно только $n$ цветов.

Определения

Как и в случае вершинной раскраски, рёберная раскраска графа, если не указано явно другое, всегда предполагает, что двум смежным рёбрам назначаются различные цвета. Два ребра считаются смежными, если они имеют общую вершину. Рёберную раскраску графа $G$ можно рассматривать как эквивалент вершинной раскраски рёберного графов $L(G)$, графа, имеющего по вершине для каждого ребра графа $G$ и по ребру для каждой пары смежных рёбер $G$.

Правильная раскраска $k$ различными цветами называется (правильной) рёберной $k$-раскраской. Если для графа можно найти (правильную) рёберную $k$-раскраску, говорят, что он рёберно $k$-раскрашиваем. Наименьшее число цветов, необходимых для (правильной) рёберной раскраски графа $G$ называется хроматическим индексом, или рёберным хроматическим числом $\chi {\prime }(G)$. Хроматический индекс иногда записывается в виде $\chi _{1}(G)$. В этой нотации индекс показывает, что рёбра являются одномерными объектами. Граф является рёберно $k$-цветным, если хроматический индекс в точности равен $k$. Хроматический индекс не следует путать с хроматическим числом $\chi (G)$ или $\chi _{0}(G)$, минимальным числом цветов, необходимых для правильной раскраски вершин графа $G$.

Если не указано противное, все графы предполагаются простыми, в противоположность мультиграфам, у которых два и более ребра могут соединять одну и ту же пару вершин и в которых могут быть петли (ребро, у которого конечные вершины совпадают). Для большинства задач рёберной раскраски простые графы ведут себя отлично от мультиграфов и требуется дополнительная осторожность при распространении теорем рёберной раскраски с простых графов на мультиграфы.

Связь с паросочетаниями

Этот 3-регулярный Планарный граф имеет 16 вершин и 24 ребра, но только 7 в любом максимальном паросочетании. Таким образом, требуется четыре цвета для любой рёберной раскраски.

Паросочетанием в графе $G$ называется множество рёбер, никакие два из которых не смежны. Паросочетание называется совершенным, если его рёбра содержат все вершины графа и максимальным, если оно содержит максимально возможное число рёбер. В рёберной раскраске рёбра одного цвета должны быть несмежны, так что они образуют паросочетание. Таким образом, правильная рёберная раскраска — это то же самое, что и разложение графа на непересекающиеся паросочетания.

Если размер максимального паросочетания в заданном графе мал, необходимо большое число паросочетаний для покрытия всех рёбер графа. Выражаясь более формально, это объяснение предполагает, что если граф имеет $m$ рёбер и если максимум $\beta$ рёбер могут принадлежать максимальному паросочетанию, то каждая рёберная раскраска графа должна содержать по меньшей мере $m/\beta$ различных цветов. Например, планарный граф с 16 вершинами, показанный на иллюстрации, имеет $m=24$ рёбер. В этом графе нет совершенного паросочетания — если центральна вершина принадлежит паросочетанию, оставшиеся вершины можно разбить на три связных группы с числом вершин 4, 5, 5. Получившиеся подграфы с нечётным числом вершин не имеют совершенного паросочетания. Тем не менее, граф имеет максимальное паросочетание с семью рёбрами, так что $\beta =7$. Поэтому число цветов, необходимых для рёберной раскраски графа, равно как минимум 24/7, а поскольку число цветов должно быть целым, получаем как минимум 4 цвета.

Для регулярных графов степени $k$, не имеющих совершенного паросочетания, эта нижняя граница может быть использована, чтобы показать, что необходимо как минимум $k+1$ цветов. В частности, это верно для регулярных графов с нечётным числом вершин. Для таких графов, по лемме о рукопожатиях, $k$ должно быть, в свою очередь, чётным. Однако неравенство $\chi {\prime }\geqslant m\beta$ не полностью объясняет хроматический индекс произвольного регулярного графа, поскольку есть регулярные графы, имеющие совершенное паросочетание, но не рёберно k-раскрашиваемы. Например, граф Петерсена регулярен с $m=15$ и с $\beta =5$ рёбрами в совершенном паросочетании, но он не имеет рёберной 3-раскраски.

Связь со степенью

Теорема Визинга

Рёберное хроматическое число графа $G$ тесно связано с максимальной степенью ${\Delta }(G)$ (максимальное число рёбер, инцидентных любой отдельной вершине графа $G$). Ясно, что $\chi {\prime }(G)\geq {\Delta }(G)$, так что если ${\Delta }$ различных рёбер содержат вершину $v$, то все эти рёбра должны быть раскрашены в различные цвета, что возможно только если имеется как минимум $\Delta$ цветов. Теорема Визинга (названа в честь Вадима Визинга, опубликовавшего её в 1964 году) утверждает, что эта граница почти точна — для любого графа рёберное хроматическое число равно либо ${\Delta }(G)$, либо $\Delta (G)+1$. Если $\chi {\prime }(G)={\Delta }(G)$, говорят, что G имеет класс 1, в противном случае говорят о классе 2.

Любой двудольный граф имеет класс 1 и почти все случайные графы имеют класс 1. Однако задача проверки, имеет ли произвольный граф класс 1, является NP-полной задачей.

Визинг доказал, что планарные графы максимальной степени не менее восьми имеют класс 1 и высказал гипотезу, что то же самое верно для планарных графов степени 7 или 6. С другой стороны, существуют планарные графы с максимальной степенью от двух до пяти, имеющие класс 2. С тех пор гипотеза доказана для семи. Планарные графы без мостов, Кубические графы имеют класс 1, и это равносильно формулировке задачи о четырёх красках.

Регулярные графы

1-факторизация k-регулярного графа, то есть разложение рёбер графа в совершенные паросочетания — это то же самое, что и рёберная k-раскраска графа. Таким образом, регулярный граф имеет 1-факторизацию тогда и только тогда, когда он имеет класс 1. Частный случай, рёберная 3-цветная раскраска кубических (3-регулярных) графов иногда называется раскраской Тайта.

Не всякий регулярный граф имеет 1-факторизацию. Например, Граф Петерсена не имеет. Снарки определяются как графы, которые, подобно графу Петерсена, не имеют мостов, 3-регулярны и имеют класс 2.

Согласно теореме Кёнига, любой двудольный регулярный граф имеет 1-факторизацию. Теорема сформулирована ранее в терминах проективных конфигураций и доказана Эрнстом Штайницем.

Мультиграфы

Мультиграф Шеннона шестой степени, рёберной кратности три требует девяти цветов для рёберной раскраски

Для мультиграфов, в которых несколько рёбер могут соединять те же самые две вершины, известны похожие на теорему Визинга, но более слабые результаты относительно рёберного хроматического числа $\chi {\prime }(G)$, максимальной степени $\Delta (G)$ и кратности $\mu (G)$, максимального числа рёбер в связке параллельных рёбер (то есть имеющих одни и те же конечные вершины). В качестве простого примера, показывающего, что теорема Визинга не обобщается на мультиграфы, рассмотрим мультиграф Шеннона, мультиграф с тремя вершинами и тремя связками $\mu (G)$ параллельных рёбер, соединяющих каждую пару вершин. В этом примере: $\Delta (G)=2\mu (G)$ — каждая вершина смежна только двум из трёх связок $\mu (G)$ параллельных рёбер, но рёберное хроматическое число равно $3\mu (G)$ (в графе $3\mu (G)$ рёбер и любые два ребра смежны, так что все рёбра должны быть раскрашены в разные цвета). В работе, навеянной теоремой Визинга, Сойфер и Шеннон показали, что это худший случай — $\chi {\prime }(G)\leq (3/2)\Delta (G)$ для любого мультиграфа $G$. Вдобавок, для любого мультиграфа $G$ $\chi {\prime }(G)\leq \Delta (G)+\mu (G)$. Это неравенство сводится к теореме Визинга для простых графов (для них $\mu (G)=1$).

Алгоритмы

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

Оптимальная раскраска некоторых специальных классов графов

В случае двудольных графов или мультиграфов с максимальной степенью $\Delta$, оптимальное число цветов равно в точности $\Delta$. В 2001 году показано, что оптимальная рёберная раскраска этих графов может быть найдена почти за линейное время $O(m\,\log \Delta )$, где $m$ — число рёбер в графе. Более простые, но несколько более медленные алгоритмы описаны ранее Коулом и Хопкрофтом и Алоном . Алгоритм Алона начинает с того, что делает граф регулярным без существенного увеличения степени или существенного увеличения размера путём слияния пар вершин, принадлежащих одной доле двудольного графа, а затем добавлением небольшого числа вершин и рёбер. После этого, если степень нечётна, Алон находит совершенное паросочетание за линейное время, назначает ему цвет и удаляет из графа, что приводит к графу чётной степени. Наконец, Алон использует наблюдение Габова, что выбор чередующихся подмножеств рёбер в эйлеровом цикле графа разделяет его на два регулярных подграфа, преобразуя задачу рёберной раскраски в две меньшие задачи, так что его алгоритм теперь решает эти две подзадачи рекурсивно. Полное время работы алгоритма оценивается как $O(m\,\log m)$.

Для планарных графов с максимальной степенью ${\Delta }\geq 7$ оптимальное число цветов снова равно в точности $\Delta$. При более строгом предположении, что ${\Delta }\geq 9$, можно найти оптимальную рёберную раскраску за линейное время.

Алгоритмы, использующие больше цветов, чем нужно для оптимальной раскраски

Существуют алгоритмы полиномиального времени раскраски любого графа с $\Delta +1$ цветами, что соответствует границе, задаваемой теоремой Визинга.

Для мультиграфов в 1987 году существует следующий алгоритм (приписываемый Эли Упфалу): исходный мультиграф $G$ делается эйлеровым путём добавления вершины, соединённой рёбрами со всеми вершинами нечётной степени; находится эйлеров путь, выбирается ориентация для этого пути; создаётся двудольный граф $H$, который содержит две копии каждой вершины графа $G$, по одной в каждой доле, и рёбрами из вершины $u$ в левой доле в вершину $v$ в правой доле, когда ориентированный путь имеет дугу из $u$ в $v$ в графе $G$. Далее применяется алгоритм рёберной раскраски двудольного графа для графа $H$. Каждый цвет в $H$ соответствует множеству рёбер в $G$, которое образует подграф с максимальной степенью два, то есть несвязное объединение путей и циклов так, что для каждого цвета в $H$ можно образовать три цвета в $G$. Время работы алгоритма ограничено временем раскраски двудольного графа $O(m\,\log \Delta )$ при использовании алгоритма Коула, Оста и Ширра. Число цветов, которое использует этот алгоритм, не превосходит $3\left\lceil {\frac {\Delta }{2}}\right\rceil$, что близко, но не совсем то же самое, что граница Шеннона $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$. То же самое можно сделать с помощью параллельного алгоритма напрямую. В той же статье Карлофф и Шмойс предлагают также алгоритм с линейным временем работы для раскраски мультиграфов максимум третьей степени четырьмя цветами (что удовлетворяет как границе Шеннона, так и границе Визинга). Этот алгоритм работает по похожим принципам — алгоритм также добавляет вершину, чтобы сделать граф эйлеровым, находит эйлеров путь, а затем выбирает чередующиеся множества рёбер в пути чтобы разбить граф на два подмножества максимальной степени два. Пути и чётные циклы каждого подмножества можно выкрасить двумя цветами (по два цвета на подграф). Следующим шагом раскрашиваются рёбра нечётных циклов, в которых по меньшей мере одно ребро может быть раскрашено одним из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечётного цикла оставляет путь, который можно раскрасить двумя цветами.

Алгоритм жадной раскраски, выбирающий последовательно рёбра графа или мультиграфа и назначающий первый допустимый цвет, может иногда использовать $2{\Delta }-1$ цветов, что может почти вдвое превосходить необходимое число цветов. Однако он имеет то преимущество, что может быть использован в онлайн алгоритмах, ничего не знающих заранее о структуре графа. При указанных условиях его конкурентный коэффициент равен двум, и этот коэффициент оптимален — никакой другой алгоритм не может дать показатели лучше. Однако, если рёбра поступают в случайном порядке и исходный граф имеет степень как минимум логарифмическую, можно получить меньший конкурентный коэффициент.

Некоторые авторы высказали гипотезу, что дробный хроматический индекс любого мультиграфа (число, которое можно вычислить за полиномиальное время с помощью линейного программирования) отличается от хроматического индекса не более чем на единицу. Если гипотеза верна, можно будет находить число, не отличающееся от хроматического индекса более чем на единицу в случае мультиграфов, что соответствует теореме Визинга для простых графов. Хотя, в общем случае, гипотеза не доказана, известно, что она верна, если хроматический индекс не меньше чем ${\Delta }+{\sqrt {{\Delta }/2}}$, точно так же, как в случае мультиграфов с достаточно большой кратностью.

Точные алгоритмы

Просто проверить, можно ли рёберно раскрасить граф одним или двумя цветами так, что первый нетривиальный случай раскраски — проверка, можно ли раскрасить граф рёберно тремя цветами. В 2009 году показано, что проверить, существует ли рёберная раскраска графа тремя цветами, можно за время $O(1.344^{n})$ при использовании лишь полиномиального пространства. Хотя эти временные границы экспоненциальны, это существенно быстрее, чем алгоритм поиска грубой силой путём просмотра всех возможных раскрасок рёбер. Любой двусвязный 3-регулярный граф с $n$ вершинами имеет $O(2^{n/2})$ рёберных 3-раскрасок. И всех их можно перечислить за время $O(2^{n/2})$ (чуть медленнее времени поиска одной раскраски). Как заметил Куперберг, граф призмы над $n/2$-угольником, имеет много раскрасок, что показывает, что эта граница точна.

При применении точных алгоритмов раскраски вершин рёберного графа, можно рёберно раскрасить оптимально любой граф с $m$ рёбрами, независимо от числа необходимых цветов за время $2^{m}m^{O(1)}$, используя экспоненциальное пространство, или за время $O(2.2461^{m})$ и полиномиальное пространство.

Поскольку задача рёберной раскраски является NP-полной даже для трёх цветов, вряд ли она поддаётся фиксированной параметризации по числу цветов. Однако задача поддаётся параметризации по другим параметрам. В частности, Чжоу, Накано и Нишизеки показали, что для графов с древесной шириной $w$ оптимальная рёберная раскраска может быть найдена за время $O(nw(6w)^{w(w+1)/2})$, которое растёт экспоненциально от $w$, но лишь линейно от числа вершин графа $n$.

В 1991 году задача рёберной раскраски сформулирована как задача целочисленного программирования и проведены эксперименты использования пакетов целочисленного программирования для рёберной раскраски графов, однако какого-либо анализа сложности таких алгоритмом не приведено.

Дополнительные свойства

Единственным образом 3-раскрашиваемый обобщённый граф Петерсена $G(9,2)$. Один из трёх цветов показан светлыми рёбрами, два других цвета можно получить поворотом этих рёбер на 40° в обоих направлениях или поочерёдным раскрашиванием гамильтонова цикла в два цвета.

Граф однозначно рёберно $k$-раскрашиваем тогда и только тогда, когда существует только один способ разбить рёбра на $k$ классов цветов, не считая $k!$ возможных перестановок цветов. Для $k\neq 3$ однозначно рёберно $k$-раскрашиваемыми графами являются только пути, циклы и звёзды, но для $k=3$ могут быть однозначно рёберно $k$-раскрашиваемыми и другие графы. Любой однозначно рёберно 3-раскрашиваемый граф имеет ровно три гамильтоновых цикла (образованных путём удаления одного из трёх цветов), однако существуют 3-регулярные графы, имеющие три гамильтоновых цикла, но не имеющие однозначной рёберной 3-раскраски, как, например, обобщённые графы Петерсена $G(6n+3,2)$ для $n\geq 2$. Известен всего один непланарный однозначно рёберно 3-раскрашиваемый граф, это обобщённый Граф Петерсена $G(9,2)$, и есть гипотеза, что других не существует.

Полный двудольный граф K_3,3 со всеми его тремя цветами, нарисованными как параллельные отрезки.

Фолкман и Фалкерсон исследовали невозрастающие последовательности чисел $m_{1},m_{2},m_{3},...$, для которых существует рёберная раскраска заданного графа $G$ с $m_{1}$ рёбрами первого цвета, $m_{2}$ рёбрами второго цвета, и так далее. Они заметили, что если последовательность $P$ подходит в описанном смысле, и если она лексикографически больше, чем последовательность $Q$ с той же суммой, то $Q$ тоже подходит. В случае, если $P>Q$ лексикографически, $P$ может быть преобразована в $Q$ пошагово, уменьшая на каждом шаге одно из чисел $m_{i}$ на единицу и увеличивая другое, идущее далее число $m_{j}$ ($i<j$), на единицу. В терминах рёберной раскраски, мы начинаем с раскраски $P$, затем последовательно обмениваем цвет $i$ и $j$ в цепи Кемпе, наибольшем пути из рёбер, чередующих два цвета. В частности, любой граф имеет справедливую рёберную раскраску, рёберную раскраску с оптимальным числом цветов, в которой два класса цветов по размеру отличаются максимум на единицу.

Теорема де Брёйна — Эрдёша может быть использована для переноса многих свойств рёберной раскраски с конечных графов на бесконечные. Например, теоремы Шеннона и Визинга о связи степени графа с его хроматическим индексом обе легко обобщаются для бесконечных графов.

В 2011 году рассмотрена задача поиска рисунка данного кубического графа со свойствами, что все рёбра в рисунке имеют один из трёх различных углов наклона и никакие два ребра не лежат на одной прямой. Если такое представление графа на рисунке существует, ясно, что угол наклона рёбер можно рассматривать как цвет рёбер в трёхцветной раскраске графа. Например, рисунок $K_{3,3}$ в виде рёбер и длинных диагоналей правильного шестиугольника представляет рёберную 3-раскраску графа таким способом. Показано, что 3-регулярный двудольный граф с заданной раскраской Тайта имеет графическое представление такого вида тогда и только тогда, когда он рёберно k-связен. Для недвудольных графов условие чуть сложнее — заданная раскраска может быть представлена такого рода рисунком, если двойное двудольное покрытие графа 3-рёберно связно и если удаление двух одинаково раскрашенных рёбер приводит к недвудольному подграфу. Все эти условия легко проверить за полиномиальное время, однако задача проверки, имеет ли рёберно 4-раскрашенный 4-регулярный граф рисунок с четырьмя углами наклона, соответствующих цветам, является полной для теории существования вещественных чисел, того же класса сложности, что и NP-полнота.

Имея связь с максимальной степенью и максимальным числом паросочетаний графа, хроматический индекс тесно связан также с древесностью $la(G)$ графа $G$, минимальному числу линейных лесов (несвязному объединению путей), на которые рёбра графа могут быть разбиты. Паросочетание — это специальный вид линейного леса, но, с другой стороны, любой линейный лес может быть рёберно 2-раскрашен, так что для любого $G$ $la(G)\leq \chi {\prime }(G)\leq 2la(G)$. Гипотеза Акияма утверждает, что $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {{\Delta }+1}{2}}\right\rceil$, откуда следовало бы более сильное неравенство $2la(G)-2\leq \chi {\prime }(G)\leq 2la(G)$. Для графов максимальной степени три $la(G)$ всегда в точности равно двум, так что ограничение $\chi {\prime }(G)\leq 2la(G)$ соответствует границе, следующей из теоремы Визинга.

Другие типы рёберной раскраски

Разбиение полного двудольного графа K_4,4 на три леса, показывающее, что граф имеет древесность три.

Число Туэ графа — это число цветов, нужных для рёберной раскраски, удовлетворяющей более сильным требованиям, чем любой путь чётной длины, а именно первая и вторая половина пути должны образовывать различные последовательности цветов.

Древесность графа — это минимальное число цветов, необходимых для раскраски таким образом, что рёбра любого цвета не содержат циклов (а не как в стандартной задаче раскраски — рёбра одного цвета несмежны). Таким образом, это минимальное число элементов леса, в которые можно разложить рёбра графа. В отличие от хроматического числа, ширина леса может быть вычислена за полиномиальное время.

Задача предписанной раскраски рёбер — это задача, в которой для заданного графа, для каждой дуги которого задан список цветов, нужно найти подходящую раскраску рёбер, в которой каждый цвет берётся из заданного списка. Предписанный хроматический индекс графа $G$ — это наименьшее число $k$, при котором независимо от выбора списков цветов для рёбер, если для каждого ребра задано не менее $k$ цветов, раскраска гарантированно существует. Предписанный хроматический индекс всегда не меньше хроматического числа. Гипотезу Диница о заполнении частичных латинских квадратов можно перефразировать как утверждение, что предписанное рёберное хроматическое число полного двудольного графа $K_{n,n}$ равно его рёберному хроматическому числу $n$. В 1995 году гипотеза разрешена, притом доказано более сильное утверждение, что для любого двудольного графа хроматический индекс и предписанный хроматический индекс равны. Высказана ещё более общая гипотеза о равенстве хроматического числа и предписанного хроматического числа для произвольных мультиграфов без петель. Эта гипотеза остаётся открытой.

Много изучавшихся вариаций задачи о вершинной раскраске распространены на рёберную раскраску. Например, задача о полной рёберной раскраске является вариантом полной раскраски, правильной раскраски вершин, при которой любая пара цветов должна присутствовать хотя бы раз в множестве сопряжённых вершин, и задача состоит в максимизации общего числа цветов. Строгая рёберная раскраска — это рёберный вариант строгой раскраски, при которой любые два ребра со смежными конечными вершинами должны иметь различные цвета. Строгая рёберная раскраска применяется в схеме размещения каналов для беспроводных сетей. Ацикличная рёберная раскраска — это вариант ациклической раскраски, в которой любые два цвета формируют ацикличный подграф (то есть, лес).

В 2008 году изучена рёберная 3-раскраска кубических графов с дополнительным свойством, что никакие два двуцветных цикла не имеют более чем одно общее ребро, в частности показано, что существование такой раскраски эквивалентно существованию рисунка графа на трёхмерной целой решётке с рёбрами на прямых, параллельных осям координат, и каждая такая прямая содержит максимум две вершины. Однако, как и в случае стандартной задачи рёберной 3-раскраски, поиск раскраски этого типа является NP-полной задачей.

Тотальная раскраска — это вид раскраски, комбинирующий вершинную и рёберную раскраски, при которой раскрашиваются как вершины, так и рёбра. Любая вершина и ребро, концом которого она является, или два смежных ребра должны иметь различные цвета, так же как и две смежных вершины. Существует гипотеза (комбинирующая теорему Визинга и теорему Брукса), что любой граф имеет тотальную раскраску, в которой число цветов не превосходит максимальной степени плюс два. Гипотеза не доказана.

Если 3-регулярный граф на поверхности рёберно 3-раскрашиваем, его двойственный граф образует триангуляцию поверхности, которая также рёберно раскрашиваема (хотя, в общем случае, рёберная раскраска неправильна) в том смысле, что каждый треугольник раскрашен в три цвета — по ребру на цвет. Другие раскраски и ориентации треугольников, вместе с другими локальными ограничениями, каким образом цвета распределяются по вершинам или граням триангуляции, можно использовать для кодировки некоторых типов геометрических объектов. Например, прямоугольные дробления (части прямоугольного разбиения прямоугольника на более мелкие прямоугольники, при этом в каждой точке встречаются три прямоугольника) можно описать комбинаторно «регулярной маркировкой», двуцветной раскраской рёбер триангуляционного графа, двойственного прямоугольному дроблению, с ограничением, что рёбра, смежные каждой вершине, образуют четыре группы рёбер идущих (по часовой стрелке) подряд. Внутри каждой группы рёбра выкрашены в один цвет и имеют одно направление. Эта маркировка двойственна раскраске самого дробления, в которой вертикальные рёбра имеют один цвет, а горизонтальные — другой. Похожие локальные ограничения на порядок следования раскрашенных рёбер для вершины могут быть использованы для кодирования вложения планарных графов в сетку, образованную прямыми линиями, и трёхмерных многогранников с гранями, параллельными координатным плоскостям. Для каждого из этих трёх типов регулярной маркировки множество регулярных маркировок образует дистрибутивную решётку, которая может быть использована для быстрого перечисления всех геометрических структур, основанных на том же графе, или найти структуру, удовлетворяющую дополнительным ограничениям.

Детерминированный конечный автомат может быть представлен как ориентированный граф, в котором каждая вершина имеет одну и ту же полустепень исхода вершин и в котором рёбра $d$-раскрашены таким образом, что любые два ребра с одной и той же начальной вершиной имеют различные цвета. Задача о раскраске дорог — это задача рёберной раскраски направленного графа с одной и той же полустепенью исхода, такой что результирующий автомат имеет синхронизирующее слово. Трахтман(Трахтман 2009) решил задачу раскраски дорог, доказав, что такая раскраска может быть найдена, если заданный граф сильно связен и апериодичен.

Теорема Рамсея касается задачи $k$-раскраски рёбер большого полного графа $K_{n}$ с целью избежать создания одноцветных полных подграфов $K_{s}$ некоторого заданного размера $s$. Согласно теореме, существует число $R_{k}(s)$ такое, что при $n\geq R(s)$ указанная раскраска невозможна. Например, $R_{2}(3)=6$, что означает, что если рёбра графа $K_{6}$ 2-раскрашены, всегда найдётся монохромный треугольник.

Приложения

Рёберная раскраска полных графов может быть использована для разбиения расписания в круговых турнирах в несколько кругов, так чтобы каждая пара играла в одном из кругов. В этом приложении вершины соответствуют участникам турнира, а рёбра соответствуют играм. Цвет рёбер ответствует кругам турнира. Похожая техника раскраски может быть использована для составления других спортивных расписаний, в которых не обязательно каждый играет с каждым. Например, в национальной футбольной лиге (США, Американский футбол), пары команд, которые будут играть в данном году, определены результатами команд в предыдущем году, а алгоритм рёберной раскраски применяется к графу, образованному множеством этих пар с целью распределить игры на выходные, по которым игры происходят. Для этого приложения теорема Визинга означает, что не имеет значения, какое множество пар выбрано (если никакие две команды не играют дважды в сезон), всегда имеется возможность найти расписание, которое захватывает максимум одни лишние выходные (по сравнению с числом игр одной команды).

Расписание для открытой линии — это задача планирования процесса производства, в котором имеется множество объектов, требующих изготовления. Каждый объект должен пройти некоторые процедуры (в любом порядке) и каждая работа должна быть проведена на определённой машине, при этом машина одновременно может выполнять только одну процедуру. Если все работы имеют одну и ту же длину, то задачу можно поставить как рёберную раскраску двудольного графа, в которой вершины одной доли представляют объекты, которые следует изготовить, а вершины другой доли графа представляют обрабатывающие машины. Рёбра представляют работы, которые необходимо выполнить, а цвета представляют временны́е интервалы, в которых работы должны быть выполнены. Поскольку рёберная раскраска двудольного графа может быть выполнена за полиномиальное время, то это же верно и для указанного специального случая расписания для открытой линии.

В 2005 году изучена задача расписания соединения для протокола связи множественного доступа с разделением по времени в беспроводных сенсорных сетях, как вариант рёберной раскраски. В этой задаче нужно выбрать временны́е промежутки для рёбер беспроволочной сети так, что каждая вершина сети может связываться с соседними вершинами без взаимного влияния. Использование строгой рёберной раскраски (при двух временных промежутках для каждого цвета рёбер, по одному в каждом направлении) решает задачу, но число используемых промежутком может оказаться больше, чем необходимо. Вместо этого они искали раскраску ориентированного графа, образованного заменой каждого неориентированного ребра двумя ориентированными дугами, при этом каждая дуга $uv$ должна иметь цвет, отличный от цветов дуг, исходящих из $v$ и соседей $v$. Они предложили эвристический алгоритм для решения этой задачи, основанный на распределённом алгоритме для рёберного $({\Delta }+1)$-раскрашивания с последующим процессом исправления расписания для удаления возможных взаимных помех.

В волоконно-оптической связи задача назначения цвета — это задача назначения частоты света паре вершин, для которых необходима связь, и путей через оптоволоконную сеть для каждой пары, при этом существует ограничение, что никаких два пути не используют для общего сегмента волокна одну и ту же частоту. Путям, проходящим через один и тот же коммутатор, но не через один и тот же сегмент оптоволокна, разрешается иметь одну и ту же частоту. Если сеть построена в виде звезды с единственным коммутатором в центре, который соединён отдельным оптоволокном с каждой вершиной сети, задача назначения цвета может быть смоделирована в точности как задача раскраски рёбер графа или мультиграфа, в котором коммуникационные узлы образуют вершины графа, пары узлов, которым необходим обмен информацией, образуют дуги, а частота, которую можно использовать для каждой пары узлов, соответствуют раскраске дуг в задаче раскраски. Для сетей связи, имеющих более общую топологию дерева, локальные решения задач назначения цвета пути для звёзд, образованных каждым коммуникатором, могут быть собраны вместе, чтобы получить единое глобальное решение.

Открытые проблемы

Йенсен и Тофт перечислили 23 открытых проблемы, касающихся рёберной раскраски. Они включают:

• Гипотеза Голдберга, что хроматический индекс и дробный индекс отличаются не более чем на единицу, что позволило бы аппроксимировать хроматический индекс с ошибкой в один цвет за полиномиальное время.
• Некоторые гипотезы Якобсена (Jakobsen) и других авторов о структуре критических графов для рёберной раскраски графов класса 2 таких, что любой подграф либо имеет меньшую максимальную степень, либо имеет класс 1. Якобсен первоначально предположил, что все критические графы имеют нечётное число вершин, но, в конечном счёте, предположение опровергнуто. Несколько других гипотез, более слабых чем эта, а также гипотезы, ограничивающие число вершин критических графов и критических мультиграфов, остаются открытыми.
• Задача Визинга классификации максимальных степеней, что возможно для планарных графов класса 2.
• Гипотеза о переполненных графах Хилтона (A. J. W. Hilton), утверждающая, что граф со степенью не меньшей $n/3$ либо имеет класс 1, либо содержит подграф той же степени $\Delta$, что и исходный граф, а для нечётного числа вершин $k$ такой, что число рёбер подграфа больше $\Delta (k-1)/2$. Близка к этой гипотеза Герберта Грёча и Пола Сеймура относительно планарных графов вместо графов высокой степени.
• Гипотеза Четвинда (Chetwynd) и Хилтона (Hilton) (возможно, имеющая корни в более ранних работах Дирака), что регулярный граф с чётным числом вершин $n$ и степенью как минимум $n/2$ имеет класс 1.
• Гипотеза Клода Бержа и Делберта Фалкерсона, что 6-регулярные мультиграфы, образованные удвоением каждого ребра 3-регулярного простого графа без мостов, можно раскрасить шестью цветами.
• Гипотеза Фьорини и Вилсона, что любые планарные графы без треугольников, отличные от клешни K_1,3, не раскрашиваемы рёберно однозначно в 3 цвета.

Примечательна также более современная гипотеза: если $G$ является $d$-регулярным планарным мультиграфом, то $G$ рёберно $d$-раскрашиваем тогда и только тогда, когда $G$ нечётно рёберно $d$-связен. Эту гипотезу можно рассматривать как обобщение проблемы четырёх красок для $d=3$. Мария Чудновская, Катерина Эдвардс (Katherine Edwards) и Пол Сеймур доказали, что 8-регулярный планарный мультиграф имеет рёберное хроматическое число 8.

Ссылки

• Jin Akiyama, Geoffrey Exoo, Frank Harary. Covering and packing in graphs. III. Cyclic and acyclic invariants // Mathematica Slovaca. — 1980. — Т. 30, вып. 4. — С. 405—417.
• Noga Alon. A simple algorithm for edge-coloring bipartite multigraphs // Information Processing Letters. — 2003. — Т. 85, вып. 6. — С. 301—302. — doi:10.1016/S0020-0190(02)00446-5.
• Noga Alon, Benny Sudakov, Ayal Zaks. Acyclic edge colorings of graphs // Journal of Graph Theory. — 2001. — Т. 37, вып. 3. — С. 157—167. — doi:10.1002/jgt.1010.
• Lars Dovling Andersen. On edge-colourings of graphs // Mathematica Scandinavica. — 1977. — Т. 40, вып. 2. — С. 161—175.. Как цитировано у
• K. Appel, W. Haken. Every planar map is four colorable (англ.) // Bulletin of the American Mathematical Society. — 1976. — Vol. 82, iss. 5. — P. 711—712. — doi:10.1090/S0002-9904-1976-14122-5.
• Bahman Bahmani, Aranyak Mehta, Rajeev Motwani. Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). — 2010. — С. 31—39.
• Amotz Bar-Noy, Rajeev Motwani, Joseph Naor. The greedy algorithm is optimal for on-line edge coloring // Information Processing Letters. — 1992. — Т. 44, вып. 5. — С. 251—253. — doi:10.1016/0020-0190(92)90209-E.
• C. L. Barrett, G. Istrate, V. S. A. Kumar, M. V. Marathe, S. Thite, S. Thulasidasan. Proc. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops 2006). — 2006. — С. 106. — ISBN 0-7695-2520-2. — doi:10.1109/PERCOMW.2006.129.
• Norman Biggs. Research Problems / Richard K. Guy. — American Mathematical Monthly. — 1972. — Т. 79. — С. 1018—1020.
• Norman Biggs. Second International Conference on Combinatorial Mathematics // Annals of the New York Academy of Sciences. — 1979. — Т. 319. — С. 71—81. — doi:10.1111/j.1749-6632.1979.tb32775.x.
• Andreas Bjorklund, Thore Husfeldt, Mikko Koivisto. Set partitioning via inclusion-exclusion // SIAM Journal on Computing. — 2009. — Т. 39, вып. 2. — С. 546—563. — doi:10.1137/070683933.
• Juraj Bosak. Chromatic index of finite and infinite graphs // Czechoslovak Mathematical Journal. — 1972. — Т. 22(97). — С. 272—290.
• Juraj Bosak, Jaroslav Nesetril. Complete and pseudocomplete colourings of a graph // Matematicky Casopis Slovenskej Akademie Vied. — 1976. — Т. 26, вып. 3. — С. 171—184.
• E. Burke, D. De Werra, J. Kingston. {{{заглавие}}} / J. L. Gross, J. Yellen. — CRC Press, 2004. — С. 462. — ISBN 978-1-58488-090-5.
• Guantao Chen, Xingxing Yu, Wenan Zang. Approximating the chromatic index of multigraphs // Journal of Combinatorial Optimization. — 2011. — Т. 21, вып. 2. — С. 219—246. — doi:10.1007/s10878-009-9232-y.
• Richard Cole, John Hopcroft. On edge coloring bipartite graphs // SIAM Journal on Computing. — 1982. — Т. 11, вып. 3. — С. 540—546. — doi:10.1137/0211043.
• Richard Cole, Lukasz Kowalik. New linear-time algorithms for edge-coloring planar graphs // Algorithmica. — 2008. — Т. 50, вып. 3. — С. 351—368. — doi:10.1007/s00453-007-9044-3.
• Richard Cole, Kirstin Ost, Stefan Schirra. Edge-coloring bipartite multigraphs in $O(E\log D)$ time // Combinatorica. — 2001. — Т. 21, вып. 1. — С. 5—12. — doi:10.1007/s004930170002.
• Daniel W. Cranston. Strong edge-coloring of graphs with maximum degree 4 using 22 colors // Discrete Mathematics. — 2006. — Т. 306, вып. 21. — С. 2772—2778. — doi:10.1016/j.disc.2006.03.053.
• David Eppstein. Proc. 16th Int. Symp. Graph Drawing / Ioannis G. Tollis, Marizio Patrignani. — Heraklion, Crete, 2008. — Т. 5417. — С. 78—89. — (Lecture Notes in Computer Science).
• David Eppstein. Proc. 22nd Canadian Conference on Computational Geometry (CCCG 2010). — 2010.
• Paul Erdos, Robin J. Wilson. Note on the chromatic index of almost all graphs // Journal of Combinatorial Theory. — 1977. — Т. 23, вып. 2—3. — С. 255—257. — doi:10.1016/0095-8956(77)90039-9.
• Thomas Erlebach, Klaus Jansen. The complexity of path coloring and call scheduling // Theoretical Computer Science. — 2001. — Т. 255, вып. 1—2. — С. 33—50. — doi:10.1016/S0304-3975(99)00152-8.
• S. Fiorini, R. J. Wilson. Edge-colourings of graphs. — London: Pitman, 1977. — Т. 16. — (Research Notes in Mathematics). — ISBN 0-273-01129-4.
• Jon Folkman, D. R. Fulkerson. Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967). — Chapel Hill, N.C.: Univ. North Carolina Press, 1969. — С. 561—577.
• J.-L. Fouquet, J.-L. Jolivet. Strong edge-colorings of graphs and applications to multi$k$-gons // Ars Combinatoria. — 1983. — Т. 16, вып. A. — С. 141—150.
• Alan M. Frieze, Michael Krivelevich, Benny Sudakov. The strong chromatic index of random graphs // SIAM Journal on Discrete Mathematics. — 2005. — Т. 19, вып. 3. — С. 719—727 (electronic). — doi:10.1137/S0895480104445757.
• Harold N. Gabow. Using Euler partitions to edge color bipartite multigraphs // International Journal of Computer and Information Sciences. — 1976. — Т. 5, вып. 4. — С. 345—355. — doi:10.1007/BF00998632.
• Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada. Algorithms for edge-coloring graphs. — Tohoku University, 1985.
• Harold N. Gabow, Herbert H. Westermann. Forests, frames, and games: algorithms for matroid sums and applications // Algorithmica. — 1992. — Т. 7, вып. 5—6. — С. 465—497. — doi:10.1007/BF01758774.
• F. Galvin. The list chromatic index of a bipartite multigraph // Journal of Combinatorial Theory. — 1995. — Т. 63, вып. 1. — С. 153—158. — doi:10.1006/jctb.1995.1011.
• S. Gandham, M. Dawande, R. Prakash. Proc. 24th INFOCOM. — 2005. — Т. 4. — С. 2492—2501. — ISBN 0-7803-8968-9. — doi:10.1109/INFCOM.2005.1498534.
• M. K. Gol'dberg. Multigraphs with a chromatic index that is nearly maximal // Diskret. Analiz.. — 1973. — Вып. 23. — С. 3—7, 72.. Как цитировано у .
• M. Habib, B. Peroche. Some problems about linear arboricity // Discrete Mathematics. — 1982. — Т. 41, вып. 2. — С. 219—220. — doi:10.1016/0012-365X(82)90209-6.
• Ian Holyer. The NP-completeness of edge-coloring // SIAM Journal on Computing. — 1981. — Т. 10, вып. 4. — С. 718—720. — doi:10.1137/0210055.
• Peter Horak, Ludovit Niepel. A short proof of a linear arboricity theorem for cubic graphs // Acta Mathematica Universitatis Comenianae. — 1982. — Т. 40/41. — С. 275—277.
• Tommy R. Jensen, Bjarne Toft. Graph Coloring Problems. — New York: Wiley-Interscience, 1995. — ISBN 0-471-02865-7.
• Howard J. Karloff, David Shmoys. Efficient parallel algorithms for edge coloring problems // Journal of Algorithms. — 1987. — Т. 8, вып. 1. — С. 39—52. — doi:10.1016/0196-6774(87)90026-5.
• Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre // Mathematische Annalen. — 1916. — Т. 77, вып. 4. — С. 453—465. — doi:10.1007/BF01456961.
• Lukasz Kowalik. Improved edge-coloring with three colors // Theoretical Computer Science. — 2009. — Т. 410, вып. 38—40. — С. 3733—3742. — doi:10.1016/j.tcs.2009.05.005.
• Mohammad Mahdian. On the computational complexity of strong edge coloring // Discrete Applied Mathematics. — 2002. — Т. 118, вып. 3. — С. 239—248. — doi:10.1016/S0166-218X(01)00237-2.
• Guy H. J. Meredith, E. Keith Lloyd. The footballers of Croam // Journal of Combinatorial Theory. — 1973. — Т. 15, вып. 2. — С. 161—166. — doi:10.1016/0095-8956(73)90016-6.
• J. Misra, D. Gries. A constructive proof of Vizing's Theorem // Information Processing Letters. — 1992. — Т. 41, вып. 3. — С. 131—133. — doi:10.1016/0020-0190(92)90041-S.
• Rahul Muthu, N. Narayanan, C. R. Subramanian. Improved bounds on acyclic edge colouring // Discrete Mathematics. — 2007. — Т. 307, вып. 23. — С. 3063—3069. — doi:10.1016/j.disc.2007.03.006.
• Crispin Nash-Williams. Decomposition of finite graphs into forests // Journal of the London Mathematical Society. — 1964. — Т. 39.
• George Nemhauser, Sungsoo Park. A polyhedral approach to edge coloring // Operations Research Letters. — 1991. — Т. 10, вып. 6. — С. 315—322. — doi:10.1016/0167-6377(91)90003-8.
• David A. Richter. Proc. 18th International Symposium on Graph Drawing (GD 2010) / Ulrik Brandes, Sabine Cornelsen. — Springer-Verlag, 2011. — Т. 6502. — С. 353—364. — (Lecture Notes in Computer Science). — ISBN 978-3-642-18468-0. — doi:10.1007/978-3-642-18469-7_32.
• Daniel P. Sanders, Yue Zhao. Planar graphs of maximum degree seven are class I // Journal of Combinatorial Theory. — 2001. — Т. 83, вып. 2. — С. 201—212. — doi:10.1006/jctb.2001.2047.
• P. D. Seymour. On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte // Proceedings of the London Mathematical Society. — 1979. — Т. 38, вып. 3. — С. 423—460. — doi:10.1112/plms/s3-38.3.423.
• Allen J. Schwenk. Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory. — 1989. — Т. 47, вып. 1. — С. 53—59. — doi:10.1016/0095-8956(89)90064-6.
• Claude Shannon. A theorem on coloring the lines of a network // J. Math. Physics. — 1949. — Т. 28. — С. 148—151.
• Steven S. Skiena. The Algorithm Design Manual. — Springer-Verlag, 2008. — С. 548—550. — ISBN 978-1-84800-069-8. — doi:10.1007/978-1-84800-070-4_16.. См. также [1] в Stony Brook Algorithm Repository.
• Alexander Soifer. The Mathematical Coloring Book. — Springer-Verlag, 2008. — ISBN 978-0-387-74640-1.
• P. G. Tait. Remarks on the colourings of maps // Proc. R. Soc. Edinburgh. — 1880. — Т. 10. — С. 729.
• Trahtman. The road coloring problem // Israel Journal of Mathematics. — 2009. — Т. 172, вып. 1. — С. 51—60. — doi:10.1007/s11856-009-0062-5. — arXiv:0709.0099.
• V. G. Vizing. On an estimate of the chromatic class of a p-graph // Diskret. Analiz.. — 1964. — Т. 3. — С. 25—30.
• V. G. Vizing. Critical graphs with given chromatic class // Metody Diskret. Analiz.. — 1965. — Т. 5. — С. 9—17.. (На русском.)
• D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast'janov, D. B. Shmoys. Short shop schedules // Operations Research. — 1997. — Т. 45, вып. 2. — С. 288—294. — doi:10.1287/opre.45.2.288. — .
• Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki. Edge-coloring partial $k$-trees // Journal of Algorithms. — 1996. — Т. 21, вып. 3. — С. 598—617. — doi:10.1006/jagm.1996.0061.