Введение

Проблема окрашивания рёбер графа таким образом, чтобы смежные рёбра не имели одинаковый цвет.

В теории графов, правильная окраска рёбер графа — это присвоение рёбрам графа "цветов" таким образом, чтобы любые два инцидентных ребра не имели одного и того же цвета. Например, на рисунке справа показана окраска рёбер графа красным, синим и зелёным цветами. Окраска рёбер — один из нескольких различных типов раскраски графов. Задача окраски рёбер заключается в том, можно ли раскрасить рёбра заданного графа, используя не более k различных цветов, для заданного значения k, или с минимальным возможным количеством цветов. Минимальное необходимое количество цветов для рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить тремя цветами, но нельзя раскрасить двумя цветами, следовательно, хроматический индекс показанного графа равен трём. Согласно теореме Визинга, число цветов, необходимых для окраски рёбер простого графа, равно либо его максимальной степени Δ, либо Δ+1. Для некоторых графов, таких как двудольные графы и планарные графы высокой степени, число цветов всегда равно Δ, а для мультиграфов число цветов может достигать 3Δ/2. Существуют алгоритмы полиномиального времени, которые строят оптимальные раскраски двудольных графов, и раскраски недвудольных простых графов, использующие не более Δ+1 цветов; однако, общая задача поиска оптимальной раскраски рёбер является NP-трудной, и самые быстрые известные алгоритмы для её решения требуют экспоненциального времени. Изучено множество вариаций задачи окраски рёбер, в которых присвоение цветов рёбрам должно удовлетворять условиям, отличным от отсутствия смежности. Окраска рёбер находит применение в задачах планирования и в назначении частот для волоконно-оптических сетей.

Примеры

Граф цикла может быть окрашен двумя цветами по рёбрам, если длина цикла чётная: достаточно просто чередовать два цвета по циклу. Однако, если длина нечётная, требуется три цвета. Полный граф Kn с n вершинами допускает раскраску рёбер в n − 1 цветов, когда n — чётное число; это частный случай теоремы Бараньяи. Предлагается следующая геометрическая конструкция раскраски в этом случае: разместить n точек в вершинах и центре правильного (n − 1)-угольника. Для каждого класса цветов включить одно ребро от центра к одной из вершин многоугольника и все перпендикулярные рёбра, соединяющие пары вершин многоугольника. Однако, когда n нечётное, требуется n цветов: каждый цвет можно использовать только для (n − 1)/2 рёбер, что составляет 1/n от общего числа. Несколько авторов изучали раскраску рёбер нечётных графов, где вершины представляют команды из n − 1 игроков, выбранных из пула в 2n − 1 игрока, а рёбра представляют возможные пары этих команд (при этом один игрок остаётся «лишним» в качестве судьи). Случай, когда n = 3, даёт хорошо известный граф Петерсена. Как объясняется в постановке задачи (для n = 6), игроки хотят найти расписание для этих пар, чтобы каждая команда играла каждую из своих шести игр в разные дни недели, с выходными в воскресенье для всех команд; то есть, формализуя задачу математически, они хотят найти 6-раскраску рёбер 6-регулярного нечётного графа O6. Когда n = 3, 4 или 8, раскраска рёбер On требует n + 1 цветов, но когда n = 5, 6 или 7, достаточно n цветов.

Определения

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

Правильная раскраска рёбер с использованием k различных цветов называется (правильной) k-раскраской рёбер. Граф, которому можно присвоить k-раскраску рёбер, называется k-раскрашиваемым по рёбрам. Наименьшее количество цветов, необходимое для (правильной) раскраски рёбер графа G, называется хроматическим индексом или хроматическим числом по рёбрам, χ′(G). Хроматический индекс также иногда записывается как χ₁ (G); в этой записи нижний индекс один указывает на то, что рёбра являются одномерными объектами. Граф называется k-хроматическим по рёбрам, если его хроматический индекс равен точно k. Хроматический индекс не следует путать с хроматическим числом χ(G) или χ₀(G), минимальным количеством цветов, необходимых для правильной раскраски вершин G.

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

Отношение к совпадению

Соответствие в графе G — это набор ребер, ни два из которых не смежны; идеальное соответствие — это соответствие, включающее ребра, инцидентные всем вершинам графа, а максимальное соответствие — это соответствие, включающее максимально возможное количество ребер. При раскраске ребер множество ребер одного цвета должно быть попарно несмежным, то есть образовывать соответствие. Таким образом, правильная раскраска ребер эквивалентна разбиению графа на непересекающиеся соответствия. Если размер максимального соответствия в заданном графе мал, то для покрытия всех ребер графа потребуется много соответствий. Более формально, это рассуждение подразумевает, что если граф имеет m ребер в общей сложности, и если в максимальное соответствие может входить не более β ребер, то любая раскраска ребер графа должна использовать не менее m/β различных цветов. Например, планарный граф с 16 вершинами, показанный на иллюстрации, имеет m = 24 ребра. В этом графе не может быть идеального соответствия, поскольку, если центральная вершина сопоставлена, оставшиеся несопоставленные вершины можно сгруппировать в три различных связных компоненты с четырьмя, пятью и пятью вершинами, а компоненты с нечетным числом вершин не могут быть идеально сопоставлены. Однако граф имеет максимальные соответствия с семью ребрами, то есть β = 7. Следовательно, количество цветов, необходимых для раскраски ребер графа, составляет не менее 24/7, и поскольку количество цветов должно быть целым числом, оно составляет не менее четырех. Для регулярного графа степени k, не имеющего идеального соответствия, эта нижняя граница может быть использована для доказательства того, что необходимо не менее k + 1 цветов. И почти все случайные графы относятся к классу 1. Однако определение того, является ли произвольный граф классом 1, является NP-полной задачей. Доказано, что планарные графы максимальной степени не менее восьми относятся к классу 1, и выдвинуто предположение, что то же самое верно для планарных графов максимальной степени семь или шесть. С другой стороны, существуют планарные графы максимальной степени от двух до пяти, которые относятся ко второму классу. С тех пор это предположение было доказано для графов максимальной степени семь. Все мостонеразрывные кубические планарные графы относятся к первому классу; это эквивалентная формулировка теоремы о четырех красках.

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

Факторизация на 1 k-регулярного графа, то есть разбиение ребер графа на полные паросочетания, эквивалентна k-кратной окраске ребер графа. Таким образом, регулярный граф имеет 1-факторизацию тогда и только тогда, когда он принадлежит классу 1. Частным случаем этого является 3-кратная окраска кубического (3-регулярного) графа, которая иногда называется окраской Тейта. Не каждый регулярный граф имеет 1-факторизацию; например, граф Петерсена не имеет её. В более общем смысле, snarks определяются как графы, которые, как и граф Петерсена, связны, 3-регулярны и принадлежат классу 2. Согласно теореме , каждый двудольный регулярный граф имеет 1-факторизацию. Эта теорема была сформулирована ранее в терминах проективных конфигураций и доказана Эрнстом Штайницем.

Мультиграфы

Для мультиграфов, в которых несколько параллельных ребер могут соединять одни и те же две вершины, известны результаты, аналогичные, но более слабые, чем теорема Визинга, связывающие хроматическое число ребер χ′(G), максимальную степень Δ(G) и кратность μ(G) – максимальное число ребер в любом пучке параллельных ребер. В качестве простого примера, показывающего, что теорема Визинга не обобщается на мультиграфы, рассмотрим мультиграф Шеннона, мультиграф с тремя вершинами и тремя пучками параллельных ребер, содержащими по μ(G) ребер, соединяющих каждую из трех пар вершин. В этом примере Δ(G) = 2μ(G) (каждая вершина инцидентна только двум из трех пучков по μ(G) параллельных ребер), но хроматическое число ребер равно 3μ(G) (всего 3μ(G) ребер, и любые два ребра смежны, поэтому каждому ребру необходимо присвоить отличный цвет). В результате, вдохновившем Визинга, было показано, что это наихудший случай: χ′(G) ≤ (3/2)Δ(G) для любого мультиграфа G. Кроме того, для любого мультиграфа G, χ′(G) ≤ Δ(G) + μ(G) – неравенство, которое сводится к теореме Визинга в случае простых графов (для которых μ(G) = 1).

Алгоритмы

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

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

В случае двудольных графов или мультиграфов с максимальной степенью Δ, оптимальное количество цветов равно ровно Δ. Показано, что оптимальное раскрашивание рёбер этих графов можно найти за почти линейное время O(m log Δ), где m — количество рёбер в графе; более простые, но несколько более медленные алгоритмы описаны и . Алгоритм начинается с приведения входного графа к регулярному виду, не увеличивая его степень или значительно увеличивая его размер, путём объединения пар вершин, принадлежащих к одной и той же стороне двудольного разбиения, а затем добавления небольшого количества дополнительных вершин и рёбер. Затем, если степень нечётная, Алон находит одно совершенное паросочетание за почти линейное время, присваивает ему цвет и удаляет его из графа, делая степень чётной. Наконец, Алон применяет наблюдение , что выбор чередующихся подмножеств рёбер в Эйлеровом обходе графа разбивает его на два регулярных подграфа, чтобы разделить задачу раскрашивания рёбер на две меньшие подзадачи, и его алгоритм решает эти две подзадачи рекурсивно. Общее время работы его алгоритма составляет O(m log m). Для планарных графов с максимальной степенью Δ ≥ 7, оптимальное количество цветов снова равно ровно Δ. При более строгом предположении, что Δ ≥ 9, можно найти оптимальное раскрашивание рёбер за линейное время. Для d-регулярных графов, которые являются псевдослучайными в том смысле, что их матрица смежности имеет второе по величине собственное значение (по абсолютной величине) не более d^(1−ε), d является оптимальным числом цветов.

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

и описывают алгоритмы полиномиального времени для раскраски любого графа с Δ + 1 цветами, соответствующие границе, заданной теоремой Визинга; см. алгоритм раскраски рёбер Мисры и Гриса. Для мультиграфов представлен следующий алгоритм, который они приписывают Эли Апфалу. Преобразуйте входной мультиграф G в эйлеров, добавив новую вершину, соединённую ребром с каждой вершиной нечётной степени, найдите эйлеров тур и выберите ориентацию для этого тура. Постройте двудольный граф H, в котором есть две копии каждой вершины G, по одной с каждой стороны двудольного разделения, с ребром от вершины u на левой стороне разделения к вершине v на правой стороне разделения, если ориентированный тур содержит ребро от u к v в G. Примените алгоритм раскраски рёбер двудольного графа к H. Каждый цветовой класс в H соответствует набору рёбер в G, которые образуют подграф с максимальной степенью два; то есть, непересекающееся объединение путей и циклов, поэтому для каждого цветового класса в H можно сформировать три цветовых класса в G. Время работы алгоритма ограничено временем раскраски рёбер двудольного графа, O(m log Δ) с использованием алгоритма. Количество цветов, используемых этим алгоритмом, не превышает , что близко, но не идентично пределу Шеннона. В той же статье Карлофф и Шмойс также представляют алгоритм с линейным временем работы для раскраски мультиграфов максимальной степени три четырьмя цветами (соответствующий как пределу Шеннона, так и теореме Визинга), который работает по схожим принципам: их алгоритм добавляет новую вершину, чтобы сделать граф эйлеровым, находит эйлеров тур, а затем выбирает чередующиеся наборы рёбер на этом туре, чтобы разделить граф на два подграфа с максимальной степенью два. Пути и чётные циклы каждого подграфа можно раскрасить двумя цветами для каждого подграфа. После этого шага каждый оставшийся нечётный цикл содержит по крайней мере одно ребро, которое можно раскрасить одним из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечётного цикла оставляет путь, который можно раскрасить, используя два цвета для его подграфа. Жадный алгоритм раскраски, который рассматривает рёбра графа или мультиграфа по одному, присваивая каждому ребру первый доступный цвет, иногда может использовать до 2Δ − 1 цветов, что почти вдвое превышает необходимое количество цветов. Однако он имеет преимущество, заключающееся в том, что его можно использовать в онлайн-алгоритме, в котором входной граф неизвестен заранее; в этом случае его конкурентное отношение равно двум, что является оптимальным: ни один другой онлайн-алгоритм не может достичь лучших результатов. Однако, если рёбра поступают в случайном порядке, и входной граф имеет степень, по крайней мере, логарифмическую, то можно достичь меньших конкурентных отношений. Несколько авторов выдвинули предположения, которые подразумевают, что дробный хроматический индекс любого мультиграфа (число, которое можно вычислить за полиномиальное время с использованием линейного программирования) находится в пределах единицы от хроматического индекса. Если эти предположения верны, то можно будет вычислить число, которое никогда не будет отличаться от хроматического индекса более чем на единицу в случае мультиграфа, что соответствует известным результатам теоремы Визинга для простых графов. Хотя в общем случае эти предположения не доказаны, известно, что они верны, когда хроматический индекс составляет по крайней мере , что может произойти для мультиграфов с достаточно большой кратностью.

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

Просто проверить, можно ли раскрасить рёбра графа одним или двумя цветами, поэтому первым нетривиальным случаем раскраски рёбер является проверка, имеет ли граф 3-раскраску рёбер. Как показано, можно проверить, имеет ли граф 3-раскраску рёбер за время O(1.344^n), используя только полиномиальное пространство. Хотя эта временная сложность экспоненциальна, она значительно быстрее, чем полный перебор всех возможных назначений цветов рёбрам. Каждый двусвязный 3-регулярный граф с n вершинами имеет O(2^(n/2)) 3-раскрасок рёбер; все из которых можно перечислить за время O(2^(n/2)) (немного медленнее, чем время нахождения одной раскраски); как заметил Грег Куперберг, граф призмы над n/2-угольником имеет Ω(2^(n/2)) раскрасок (нижняя, а не верхняя граница), что показывает, что эта граница точна. Применяя точные алгоритмы раскраски вершин к линейному графу входного графа, можно оптимально раскрасить рёбра любого графа с m рёбрами, независимо от количества необходимых цветов, за время 2^m * m^(O(1)) и экспоненциальное пространство, или за время O(2.2461^m) и только полиномиальное пространство. Поскольку раскраска рёбер является NP-полной даже для трёх цветов, маловероятно, что она будет эффективно решаться с фиксированными параметрами, параметризованными количеством цветов. Однако она эффективно решается для других параметров. В частности, показано, что для графов с шириной дерева w оптимальная раскраска рёбер может быть вычислена за время O(nw(6w)^(w(w+1)/2)), сложность которого зависит сверхэкспоненциально от w, но только линейно от числа n вершин графа. Авторы сформулировали задачу раскраски рёбер как целочисленную программу и описали свой опыт использования решателя целочисленного программирования для раскраски рёбер графов. Однако они не проводили анализа сложности своего алгоритма.

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

Граф называется однозначно k-краеокрашиваемым, если существует только один способ разбиения ребер на k цветовых классов, не учитывая k! возможных перестановок цветов. Для k ≠ 3 единственными однозначно k-краеокрашиваемыми графами являются пути, циклы и звезды, но для k = 3 другие графы также могут быть однозначно k-краеокрашиваемыми. Каждый однозначно 3-краеокрашиваемый граф имеет ровно три гамильтоновых цикла (получаемых удалением одного из трех цветовых классов), но существуют 3-регулярные графы, имеющие три гамильтоновых цикла и не являющиеся однозначно 3-краеокрашиваемыми, например, обобщенные графы Петерсена G(6n + 3, 2) для n ≥ 2. Единственный известный неплоский однозначно 3-краеокрашиваемый граф — это обобщенный граф Петерсена G(9, 2), и предполагается, что других не существует. Исследовались неубывающие последовательности чисел m1, m2, m3, …, обладающие свойством, что существует правильная раскраска ребер заданного графа G с m1 ребрами первого цвета, m2 ребрами второго цвета и т. д. Было замечено, что если последовательность P осуществима в этом смысле и лексикографически больше последовательности Q с той же суммой, то Q также осуществима. Действительно, если P > Q в лексикографическом порядке, то P можно преобразовать в Q последовательностью шагов, каждый из которых уменьшает одно из чисел mi на единицу и увеличивает другое последующее число mj с i < j на единицу. В терминах раскраски ребер, начиная с раскраски, реализующей P, каждый из этих шагов может быть выполнен путем обмена цветов i и j на цепи Кемпе — максимальном пути ребер, чередующихся между двумя цветами. В частности, любой граф имеет равномерную раскраску ребер, то есть раскраску ребер с оптимальным числом цветов, в которой размер любых двух цветовых классов отличается не более чем на единицу. Теорема Де Брюйна — Эрдеша может быть использована для переноса многих свойств раскраски ребер конечных графов на бесконечные графы. Например, теоремы Шеннона и Визинга, связывающие степень графа с его хроматическим индексом, обобщаются на бесконечные графы. Рассматривается задача нахождения графического представления заданного кубического графа с тем свойством, что все ребра на представлении имеют один из трех различных углов наклона и что никакие два ребра не лежат на одной прямой. Если такое представление существует, то углы наклона ребер могут быть использованы в качестве цветов в 3-краевой раскраске графа. Например, представление полезного графа K3,3 в виде ребер и длинных диагоналей правильного шестиугольника представляет собой 3-краевую раскраску графа таким образом. Как показывает Рихтер, 3-регулярный простой двудольный граф с заданным раскрасом Таита имеет представление такого типа, представляющее заданную раскраску, тогда и только тогда, когда граф 3-краесвязен. Для недвудольного графа условие немного сложнее: заданную раскраску можно представить графическим представлением, если двудольный двойной накрывающий граф является 3-краесвязным, и если удаление любой монохромной пары ребер приводит к подграфу, который все еще не является двудольным. Все эти условия можно легко проверить за полиномиальное время; однако задача проверки того, имеет ли 4-краеокрашенный 4-регулярный граф представление с ребрами четырех наклонов, представляющими цвета наклонами, является полной для экзистенциальной теории вещественных чисел, класса сложности, по крайней мере, столь же сложного, как NP-полная. Хроматический индекс тесно связан с максимальной степенью и максимальным числом паросочетаний графа, а также с линейной древовидностью la(G) графа G, которая представляет собой минимальное число линейных лесов (непересекающихся объединений путей), на которые можно разбить ребра графа. Паросочетание является особым видом линейного леса, и, наоборот, любой линейный лес можно 2-краеокрасить, поэтому для любого G выполняется la(G) ≤ χ′(G) ≤ 2 la(G). Гипотеза Акиямы (названная в честь Дзина Акиямы) утверждает, что , из чего следует более строго, что 2 la(G) − 2 ≤ χ′(G) ≤ 2 la(G). Для графов максимальной степени три la(G) всегда равна точно двум, поэтому в этом случае граница χ′(G) ≤ 2 la(G) совпадает с границей, данной теоремой Визинга.

Другие виды

Число Туэ графа — это количество цветов, необходимых для раскраски рёбер, удовлетворяющей более жёсткому требованию, что в каждом пути чётной длины первая и вторая половины пути образуют различные последовательности цветов. Арборитность графа — это минимальное количество цветов, требуемое для того, чтобы рёбра каждого цвета не содержали циклов (в отличие от стандартной задачи раскраски рёбер, где требуется отсутствие смежных пар рёбер). Иными словами, это минимальное количество лесов, на которые можно разбить рёбра графа. В отличие от хроматического индекса, арборитность графа может быть вычислена за полиномиальное время. Раскраска рёбер со списками — это задача, в которой задан граф, в котором каждому ребру сопоставлен список цветов, и требуется найти правильную раскраску рёбер, в которой цвет каждого ребра выбирается из списка этого ребра. Хроматический индекс списка графа G — это наименьшее число k, обладающее свойством, что, независимо от того, как выбираются списки цветов для рёбер, если каждое ребро имеет в своём списке хотя бы k цветов, то раскраска гарантирована. Таким образом, хроматический индекс списка всегда больше или равен хроматическому индексу. Гипотеза Диница о завершении частичных латинских квадратов может быть перефразирована как утверждение, что хроматический индекс списка полного двудольного графа Kn,n равен его хроматическому индексу, n. Эта гипотеза была разрешена путём доказательства, в более общем виде, того, что в каждом двудольном графе хроматический индекс и хроматический индекс списка равны. Предполагается, что равенство между хроматическим индексом и хроматическим индексом списка выполняется ещё более широко, для произвольных мультиграфов без петель; эта гипотеза остаётся открытой. Многие другие широко изучаемые варианты раскраски вершин также были расширены на раскраску рёбер. Например, полная раскраска рёбер — это вариант полной раскраски, правильная раскраска рёбер, в которой каждая пара цветов должна быть представлена хотя бы одной парой смежных рёбер, и целью является максимизация общего количества цветов. Сильная раскраска рёбер — это вариант сильной раскраски, раскраска рёбер, в которой любые два ребра с общими конечными точками должны иметь разные цвета. Сильная раскраска рёбер имеет применение в схемах распределения каналов для беспроводных сетей. Ациклическая раскраска рёбер — это вариант ациклической раскраски, раскраска рёбер, для которой любые два цветовых класса образуют ациклический подграф (то есть лес). Ациклический хроматический индекс графа, обозначаемый , — это наименьшее количество цветов, необходимое для правильной ациклической раскраски рёбер. Было предположено, что , где — максимальная степень. В настоящее время наилучшая известная граница — . Проблема становится проще, когда у графа большая окружность. В частности, существует константа такая, что если окружность графа не меньше , то . Аналогичный результат заключается в том, что для всех существует такая, что если у графа окружность не меньше , то . Изучались 3 раскраски рёбер кубических графов с дополнительным свойством, что никакие два бихроматических цикла не имеют более одного общего ребра. Было показано, что существование такой раскраски эквивалентно существованию рисунка графа на трёхмерной целочисленной решётке, с рёбрами, параллельными координатным осям, и каждой параллельной оси линии, содержащей не более двух вершин. Однако, как и в стандартной задаче раскраски 3 рёбер, поиск раскраски такого типа является NP-полной задачей. Полная раскраска — это форма раскраски, которая объединяет раскраску вершин и рёбер, требуя раскраски как вершин, так и рёбер. Любая пара вершина-ребро, ребро-ребро или две смежные вершины должны иметь разные цвета. Было предположено (в сочетании с теоремой Визинга и теоремой Брукса), что любой граф имеет полную раскраску, в которой количество цветов не превышает максимальную степень плюс два, но это остаётся недоказанным. Если 3-регулярный граф на поверхности раскрашен 3 рёбрами, его двойственный граф образует триангуляцию поверхности, которая также раскрашена (хотя, как правило, не правильно раскрашена), таким образом, что каждый треугольник имеет одно ребро каждого цвета. Другие раскраски и ориентации триангуляций с другими локальными ограничениями на расположение цветов на вершинах или гранях триангуляции могут быть использованы для кодирования различных типов геометрических объектов. Например, прямоугольные разбиения (разбиения прямоугольного разбиения на меньшие прямоугольники, с тремя прямоугольниками, встречающимися в каждой вершине) могут быть описаны комбинаторно с помощью «регулярной маркировки», двухцветной раскраски рёбер триангуляции, двойственной разбиению, с ограничением, что рёбра, инцидентные каждой вершине, образуют четыре последовательных подпоследовательности, в каждой из которых цвета одинаковы. Эта маркировка двойственна раскраске самого прямоугольного разбиения, в которой вертикальные рёбра имеют один цвет, а горизонтальные рёбра — другой. Подобные локальные ограничения на порядок, в котором окрашенные рёбра могут появляться вокруг вершины, также могут быть использованы для кодирования прямых встраиваний плоских графов в сетку и трёхмерных многогранников с осями, параллельными сторонам. Для каждого из этих трёх типов регулярных маркировок множество регулярных маркировок фиксированного графа образует дистрибутивную решётку, которая может быть использована для быстрого перечисления всех геометрических структур, основанных на одном и том же графе (например, всех многогранников, параллельных осям, имеющих один и тот же скелет), или для поиска структур, удовлетворяющих дополнительным ограничениям. Детерминированный конечный автомат может быть интерпретирован как ориентированный граф, в котором каждая вершина имеет одинаковую исходящую степень d, и в котором рёбра раскрашены d цветами таким образом, что любые два ребра с одной и той же исходной вершиной имеют разные цвета. Задача раскраски дорог — это задача раскраски рёбер ориентированного графа с равномерными исходящими степенями таким образом, чтобы полученный автомат имел синхронизирующее слово. Эта задача была решена путём доказательства того, что такую раскраску можно найти, если заданный граф сильно связный и апериодический. Теорема Рамсея касается задачи k-раскраски рёбер большого полного графа Kn, чтобы избежать создания монохромных полных подграфов Ks заданного размера s. Согласно теореме, существует число Rk(s) такое, что, если n ≥ R(s), такая раскраска невозможна. Например, 1=R2(3) = 6, то есть, если рёбра графа K6 раскрашены двумя цветами, всегда будет монохромный треугольник. Путь в раскрашенном графе называется радужным, если на нём не повторяются цвета. Граф называется радужно раскрашенным, если существует радужный путь между любой парой вершин. Раскраска рёбер графа G цветами 1..t является интервальной t-раскраской, если используются все цвета, и цвета рёбер, инцидентных каждой вершине G, различны и образуют интервал целых чисел.

Приложения

Краевые раскраски полных графов могут использоваться для составления расписания турнира по круговой системе на минимальное количество туров, чтобы каждая пара участников сыграла друг с другом в одном из туров; в этом приложении вершины графа соответствуют участникам турнира, ребра соответствуют играм, а цвета ребер соответствуют турам, в которых проводятся игры. Аналогичные методы раскраски могут также использоваться для составления расписания других спортивных соревнований, не предполагающих встреч всех с каждым; например, в Национальной футбольной лиге пары команд, которые будут играть друг с другом в течение года, определяются на основе результатов команд в предыдущем году, а затем алгоритм раскраски ребер применяется к графу, образованному набором пар, чтобы назначить игры на выходные дни, в которые они будут проводиться. Для этого применения теорема Визинга подразумевает, что независимо от выбранного набора пар (при условии, что ни одна команда не играет друг с другом дважды в одном сезоне), всегда можно найти расписание, которое использует не более чем на один выходной день больше, чем количество игр на команду. Планирование открытых цехов — это задача планирования производственных процессов, в которых имеется набор объектов, подлежащих изготовлению, каждый объект имеет набор задач, которые необходимо выполнить над ним (в любом порядке), и каждая задача должна выполняться на определенной машине, что предотвращает одновременное выполнение любой другой задачи, требующей той же машины. Если все задачи имеют одинаковую продолжительность, то эту задачу можно формализовать как задачу раскраски ребер двудольного мультиграфа, в котором вершины с одной стороны двудольного разбиения представляют объекты, подлежащие изготовлению, вершины с другой стороны двудольного разбиения представляют производственные машины, ребра представляют задачи, которые необходимо выполнить, а цвета представляют временные шаги, в которых каждая задача может быть выполнена. Поскольку раскраска ребер двудольного графа может быть выполнена за полиномиальное время, то же самое справедливо и для этого частного случая планирования открытых цехов. Рассмотрите задачу планирования каналов для протоколов связи с множественным доступом по временному разделению каналов в сенсорных сетях как вариант задачи раскраски ребер. В этой задаче необходимо выбрать временные слоты для ребер беспроводной сети связи таким образом, чтобы каждый узел сети мог взаимодействовать с каждым соседним узлом без помех. Использование сильной раскраски ребер (и использование двух временных слотов для каждого цвета ребра, по одному для каждого направления) решило бы проблему, но может потребовать больше временных слотов, чем необходимо. Вместо этого они ищут раскраску ориентированного графа, образованного удвоением каждого неориентированного ребра сети, с тем свойством, что каждое ориентированное ребро uv имеет цвет, отличный от цветов ребер, исходящих из v, и ребер, исходящих из соседей v. Они предлагают эвристику для этой задачи, основанную на распределенном алгоритме раскраски ребер (Δ + 1) вместе с этапом постобработки, который перепланирует ребра, которые могут мешать друг другу. В волоконно-оптической связи задача раскраски путей — это задача присвоения цветов (частот света) парам узлов, желающих общаться друг с другом, и путям через волоконно-оптическую сеть связи для каждой пары, с ограничением, что никакие два пути, использующие один и тот же сегмент волокна, не могут использовать одну и ту же частоту. Пути, проходящие через один и тот же коммуникационный коммутатор, но не через какой-либо сегмент волокна, могут использовать одну и ту же частоту. Когда сеть связи организована как звездная сеть с одним центральным коммутатором, соединенным отдельными волокнами с каждым узлом, задача раскраски путей может быть точно смоделирована как задача раскраски ребер графа или мультиграфа, в котором взаимодействующие узлы образуют вершины графа, пары узлов, желающих общаться, образуют ребра графа, а частоты, которые могут быть использованы для каждой пары, образуют цвета задачи раскраски ребер. Для сетей связи с более общей топологией дерева локальные решения задачи раскраски путей для звездных сетей, определенных каждым коммутатором в сети, могут быть объединены для формирования единого глобального решения.

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

Список 23 открытых проблем, касающихся окраски рёбер. Они включают в себя:
Утверждение о том, что хроматический индекс и дробный индекс отличаются не более чем на единицу, что позволило бы приблизить хроматический индекс с точностью до одного цвета за полиномиальное время. Несколько гипотез Якобсена и других относительно структуры критических графов для окраски рёбер, графов класса 2, таких что любой подграф либо имеет меньшую максимальную степень, либо принадлежит классу 1. Изначально Якобсен предположил, что все критические графы имеют нечётное число вершин, но это впоследствии было опровергнуто. Несколько других гипотез, ослабляющих данную или ограничивающих число вершин критических графов и критических мультиграфов, остаются открытыми. Проблема Визинга о классификации максимальных степеней, возможных для планарных графов класса 2. Гипотеза о переполненном подграфе А. Дж. У. Хилтона, утверждающая, что графы со степенью не менее n/3 либо принадлежат классу 1, либо содержат подграф с той же степенью Δ, что и исходный граф, и с нечётным числом вершин k, при этом число рёбер в подграфе больше, чем Δ(k − 1)/2, а также аналогичная гипотеза Герберта Гротца и Пола Сеймура, касающаяся планарных графов вместо графов высокой степени. Гипотеза Аманды Четвинд и Энтони Хилтона (возможно, восходящая к работам Габриэля Эндрю Дирака), что регулярные графы с чётным числом вершин n и степенью не менее n/2 принадлежат классу 1. Гипотеза Клода Бержа и Д. Р. Фулкерсона о том, что 6-регулярные мультиграфы, образованные удвоением каждого ребра 3-регулярного связного простого графа, могут быть окрашены по рёбрам в шесть цветов. Гипотеза Фиорини и Уилсона о том, что любой планарный граф без треугольников, за исключением когтя K1,3, не имеет единственной 3-раскраски рёбер. Гипотеза 2012 года, утверждающая, что если G — d-регулярный планарный мультиграф, то G можно раскрасить по рёбрам d цветами тогда и только тогда, когда G d-кратно связен по рёбрам. Эта гипотеза является обобщением теоремы о четырёх цветах, которая возникает при d = 3. Мария Чудновская, Кэтрин Эдвардс и Пол Сеймур доказали, что 8-регулярный планарный мультиграф имеет хроматическое число по рёбрам, равное 8.