В теории графов правильная раскраска ребер графа — это присвоение «цветов» ребрам графа так, чтобы никакие два инцидентных ребра не имели одинаковый цвет. Например, на рисунке справа показана раскраска ребер графа в красный, синий и зеленый цвета. Раскраска ребер — это один из нескольких различных типов раскраски графа . Задача раскраски ребер спрашивает, можно ли раскрасить ребра данного графа, используя не более k разных цветов, для заданного значения k или наименьшего количества возможных цветов. Минимально необходимое количество цветов для ребер данного графа называется хроматическим индексом графа. Например, ребра графа на иллюстрации можно раскрасить тремя цветами, но нельзя раскрасить двумя цветами, поэтому показанный граф имеет хроматический индекс три.
По теореме Визинга количество цветов, необходимых для раскраски ребер простого графа, равно либо его максимальной степени Δ , либо Δ+1 . Для некоторых графов, таких как двудольные графы и планарные графы высокой степени , количество цветов всегда равно Δ , а для мультиграфов количество цветов может достигать 3Δ/2 . Существуют алгоритмы с полиномиальным временем, которые строят оптимальные раскраски двудольных графов, а также раскраски недвудольных простых графов, использующие не более Δ+1 цветов; однако общая проблема поиска оптимальной раскраски ребер является NP-трудной , и самые быстрые из известных алгоритмов для ее решения требуют экспоненциального времени. Было изучено множество вариантов задачи о раскраске ребер, в которой присвоение цветов ребрам должно удовлетворять другим условиям, кроме несмежности. Раскраска границ находит применение в задачах планирования и присвоении частот для оптоволоконных сетей.
Ребра графа циклов могут быть окрашены в два цвета, если длина цикла четная: просто чередуйте два цвета вокруг цикла. Однако, если длина нечетная, необходимы три цвета. [1]
Полный граф K n с n вершинами можно раскрасить по ребрам в n − 1 цвет, если n — четное число; это частный случай теоремы Бараньи . Сойфер (2008) в этом случае предлагает следующую геометрическую конструкцию раскраски: поместите n точек в вершины и центр правильного ( n - 1) -стороннего многоугольника. Для каждого цветового класса включите одно ребро от центра к одной из вершин многоугольника и все перпендикулярные края, соединяющие пары вершин многоугольника. Однако, когда n нечетно, необходимо n цветов: каждый цвет можно использовать только для ( n − 1)/2 ребер, что составляет 1/ n долю от общего числа. [2]
Несколько авторов изучали раскраски ребер нечетных графов , n -регулярных графов, в которых вершины представляют команды из n - 1 игроков, выбранных из пула из 2 n - 1 игроков, и в которых ребра представляют возможные пары этих команд (с один игрок остался «лишним» судить игру). Случай, когда n = 3, дает известный граф Петерсена . Как объясняет Биггс (1972) проблему (для n = 6 ), игроки хотят найти расписание для этих пар так, чтобы каждая команда играла каждую из своих шести игр в разные дни недели, а воскресенья были выходными для всех команд; то есть, формализуя задачу математически, они хотят найти 6-реберную раскраску 6-регулярного нечетного графа O 6 . Когда n равно 3, 4 или 8, для раскраски ребер On требуется n + 1 цветов, но когда оно равно 5, 6 или 7, требуется только n цветов. [3]
Как и в случае с его аналогом вершин , раскраска ребер графа, когда она упоминается без каких-либо уточнений, всегда считается правильной раскраской ребер, то есть никаким двум соседним ребрам не присвоен один и тот же цвет. Здесь два различных ребра считаются смежными, если они имеют общую вершину. Раскраску ребер графа G можно также рассматривать как эквивалент раскраски вершин линейного графа L ( G ) , графа, который имеет вершину для каждого ребра G и ребро для каждой пары смежных ребер в G.
Правильная раскраска ребер k различными цветами называется (правильной) k -раскраской ребер. Граф, которому можно присвоить k -раскраску ребер, называется k -раскраской ребер. Наименьшее количество цветов, необходимое для (правильной) раскраски ребер графа G , — это хроматический индекс или хроматическое число ребер, χ′( G ) . Хроматический индекс также иногда записывают с использованием обозначения χ 1 ( G ) ; в этих обозначениях нижний индекс указывает, что ребра являются одномерными объектами. Граф является k- реберно-хроматическим, если его хроматический индекс равен в точности k . Хроматический индекс не следует путать с хроматическим числом χ( G ) или χ0 ( G ) , минимальным количеством цветов, необходимых для правильной раскраски вершин G.
Если не указано иное, все графы считаются простыми, в отличие от мультиграфов , в которых два или более ребра могут соединять одну и ту же пару конечных точек и в которых могут быть петли. Для многих задач раскраски ребер простые графы ведут себя иначе, чем мультиграфы, и требуется дополнительная осторожность, чтобы распространить теоремы о раскраске ребер простых графов на случай мультиграфов.
Паросочетание в графе G — это набор ребер, никакие два из которых не являются смежными ; идеальное паросочетание — это паросочетание, включающее в себя ребра, соприкасающиеся со всеми вершинами графа, а максимальное паросочетание — это паросочетание, включающее как можно больше ребер. При раскраске ребер набор ребер любого одного цвета должен быть несмежным друг с другом, чтобы они образовывали совпадение. То есть правильная раскраска ребер — это то же самое, что разбиение графа на непересекающиеся паросочетания.
Если размер максимального паросочетания в данном графе невелик, то потребуется много паросочетаний, чтобы охватить все ребра графа. Выражаясь более формально, это рассуждение подразумевает, что если граф имеет всего m ребер и если не более β ребер могут принадлежать максимальному паросочетанию, то каждая раскраска ребер графа должна использовать как минимум m /β разных цветов. [4] Например, показанный на рисунке плоский граф с 16 вершинами имеет m = 24 ребра. В этом графе не может быть идеального паросочетания; ибо, если центральная вершина совпадает, оставшиеся несовпадающие вершины могут быть сгруппированы в три разных связных компонента с четырьмя, пятью и пятью вершинами, а компоненты с нечетным числом вершин не могут быть идеально совмещены. Однако граф имеет максимальное количество паросочетаний с семью ребрами, поэтому β = 7 . Следовательно, количество цветов, необходимых для раскраски ребер графа, составляет не менее 24/7, а поскольку количество цветов должно быть целым числом, оно должно быть не менее четырех.
Для регулярного графа степени k , не имеющего идеального паросочетания, эту нижнюю оценку можно использовать, чтобы показать, что требуется как минимум k + 1 цвет. [4] В частности, это верно для регулярного графа с нечетным числом вершин (например, нечетных полных графов); для таких графов по лемме о согласовании k само должно быть четным . Однако неравенство χ′ ≥ m /β не полностью объясняет хроматический индекс каждого регулярного графа, поскольку существуют регулярные графы, которые имеют идеальные паросочетания, но не раскрашиваются по k -ребрам. Например, граф Петерсена является регулярным, с m = 15 и β = 5 ребрами в его совершенных паросочетаниях, но не имеет 3-раскраски ребер.
Хроматическое число ребер графа G очень тесно связано с максимальной степенью Δ( G ) , наибольшим количеством ребер, инцидентных любой отдельной вершине G. Очевидно, χ′( G ) ≥ ∆( G ) , поскольку если ∆ разные ребра встречаются в одной и той же вершине v , то всем этим ребрам нужно присвоить разные цвета друг от друга, а это возможно только в том случае, если существуют для назначения доступно как минимум Δ цветов. Теорема Визинга (названная в честь Вадима Г. Визинга , опубликовавшего ее в 1964 году) утверждает, что эта граница почти точна: для любого графа реберное хроматическое число равно либо Δ( G ) , либо Δ( G ) + 1 . Когда χ′( G ) = ∆( G ) , говорят, что G относится к классу 1; в противном случае говорят, что он относится к классу 2.
Каждый двудольный граф относится к классу 1, [5] и почти все случайные графы относятся к классу 1. [6] Однако NP-полно определить, принадлежит ли произвольный граф к классу 1. [7]
Визинг (1965) доказал, что плоские графы максимальной степени не ниже восьми относятся к первому классу, и предположил, что то же самое верно для плоских графов максимальной степени семь или шесть. С другой стороны, существуют плоские графы максимальной степени от двух до пяти, относящиеся к второму классу. С тех пор гипотеза была доказана для графов максимальной степени семь. [8] Все плоские кубические графы без мостов относятся к классу 1; это эквивалентная форма теоремы о четырех цветах . [9]
1 -факторизация k - регулярного графа , разбиение ребер графа на совершенные паросочетания , — это то же самое, что k - раскраска ребер графа. То есть регулярный граф имеет 1-факторизацию тогда и только тогда, когда он принадлежит к классу 1. Как частный случай этого, 3-реберную раскраску кубического ( 3-регулярного) графа иногда называют раскраской Тейта .
Не каждый регулярный граф имеет 1-факторизацию; например, график Петерсена этого не делает. В более общем смысле снарки определяются как графы, которые, как и граф Петерсена, не имеют мостов, 3-регулярны и относятся к классу 2.
Согласно теореме Кенига (1916), каждый двудольный регулярный граф имеет 1-факторизацию. Теорема была сформулирована ранее в терминах проективных конфигураций и доказана Эрнстом Стейницем .
Для мультиграфов , в которых несколько параллельных ребер могут соединять одни и те же две вершины, известны результаты, аналогичные теореме Визинга, но более слабые, связанные с хроматическим числом ребра χ'( G ) , максимальной степенью Δ( G ) и кратностью µ ( G ) максимальное количество ребер в любом пучке параллельных ребер. В качестве простого примера, показывающего, что теорема Визинга не обобщается на мультиграфы, рассмотрим мультиграф Шеннона , мультиграф с тремя вершинами и тремя пучками параллельных ребер µ( G ) , соединяющих каждую из трех пар вершин. В этом примере Δ( G ) = 2μ( G ) (каждая вершина инцидентна только двум из трех пучков параллельных ребер µ( G ) ), но хроматическое число ребра равно 3μ( G ) (существует 3μ( G ) ) ребер в общей сложности, и каждые два ребра являются смежными, поэтому всем ребрам необходимо присвоить друг другу разные цвета). В результате, вдохновившем Визинга, Шеннон (1949) [10] показал, что это худший случай: χ′( G ) ≤ (3/2)Δ( G ) для любого мультиграфа G . Кроме того , для любого мультиграфа G χ′( G ) ≤ Δ( G ) + µ( G ) - неравенство, которое сводится к теореме Визинга в случае простых графов (для которых µ( G ) = 1 ).
Поскольку задача проверки того, принадлежит ли граф к классу 1, является NP-полной , не существует известного алгоритма с полиномиальным временем для раскраски ребер каждого графа в оптимальное количество цветов. Тем не менее, был разработан ряд алгоритмов, которые ослабляют один или несколько из этих критериев: они работают только с подмножеством графов, или не всегда используют оптимальное количество цветов, или не всегда работают за полиномиальное время.
В случае двудольных графов или мультиграфов с максимальной степенью Δ оптимальное количество цветов равно Δ . Коул, Ост и Ширра (2001) показали, что оптимальная раскраска ребер этих графов может быть найдена за почти линейную временную границу O( m log Δ) , где m — количество ребер в графе; более простые, но несколько более медленные алгоритмы описаны Коулом и Хопкрофтом (1982) и Алоном (2003). Алгоритм Алона (2003) начинается с того, что делает входной граф регулярным, без увеличения его степени или существенного увеличения его размера, путем слияния пар вершин, принадлежащих одной и той же стороне бираздела, а затем добавления небольшого количества дополнительных вершин и ребер. . Затем, если степень нечетная, Алон находит одно идеальное совпадение за почти линейное время, присваивает ему цвет и удаляет его из графика, в результате чего степень становится четной. Наконец, Алон применяет наблюдение Габоу (1976) о том, что выбор чередующихся подмножеств ребер в эйлеровом обходе графа разбивает его на два регулярных подграфа, чтобы разделить проблему раскраски ребер на две меньшие подзадачи, и его алгоритм решает две подзадачи. рекурсивно . Общее время работы его алгоритма составляет O( m log m ) .
Для плоских графов с максимальной степенью Δ ≥ 7 оптимальное количество цветов снова равно точно Δ . При более сильном предположении, что Δ ≥ 9 , можно найти оптимальную раскраску ребер за линейное время (Cole & Kowalik 2008).
Для d-регулярных графов, которые являются псевдослучайными в том смысле, что их матрица смежности имеет второе по величине собственное значение (по абсолютному значению) не более d 1−ε , d — оптимальное количество цветов (Ferber & Jain 2020).
Мисра и Грис (1992) и Габоу и др. (1985) описывают алгоритмы с полиномиальным временем для раскраски любого графа в Δ + 1 цвет, соответствующие границе, заданной теоремой Визинга; см. Алгоритм окраски ребер Мисры и Гриса .
Для мультиграфов Карлофф и Шмойс (1987) представляют следующий алгоритм, который они приписывают Эли Упфалу . Сделайте входной мультиграф G эйлеровым , добавив новую вершину, соединенную ребром, с каждой вершиной нечетной степени, найдите эйлеров обход и выберите ориентацию для обхода. Сформируйте двудольный граф H , в котором есть две копии каждой вершины G , по одной на каждой стороне двураздела, с ребром от вершины u на левой стороне двураздела до вершины v на правой стороне двураздела. всякий раз, когда ориентированный тур имеет ребро от u до v в G . Примените алгоритм раскраски ребер двудольного графа к H . Каждый цветовой класс в H соответствует набору ребер в G , которые образуют подграф с максимальной степенью два; то есть непересекающееся объединение путей и циклов, поэтому для каждого цветового класса в H можно сформировать три цветовых класса в G . Время работы алгоритма ограничено временем раскраски ребер двудольного графа, O( m log Δ) с использованием алгоритма Коула, Оста и Ширры (2001). Число цветов, которые использует этот алгоритм, не превышает 0 , близко к границе Шеннона, но не совсем такой же . Его также можно простым способом превратить в параллельный алгоритм . В той же статье Карлофф и Шмойс также представляют алгоритм с линейным временем для раскраски мультиграфов максимальной степени три в четыре цвета (соответствующий границам Шеннона и Визинга), который работает на аналогичных принципах: их алгоритм добавляет новую вершину, чтобы сделать граф эйлеровым, находит обход Эйлера, а затем выбирает чередующиеся наборы ребер в обходе, чтобы разбить граф на два подграфа максимальной степени два. Пути и даже циклы каждого подграфа могут быть раскрашены в два цвета на каждый подграф. После этого шага каждый оставшийся нечетный цикл содержит хотя бы одно ребро, которое можно раскрасить в один из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечетного цикла оставляет путь, который можно раскрасить двумя цветами его подграфа.
Жадный алгоритм раскраски , который рассматривает ребра графа или мультиграфа одно за другим, присваивая каждому ребру первый доступный цвет, иногда может использовать до 2Δ - 1 цветов, что может быть почти в два раза больше цветов, чем необходимо. Однако у него есть то преимущество, что его можно использовать в настройках онлайн-алгоритма , в которых входной граф заранее не известен; в таких условиях его коэффициент конкурентоспособности равен двум, и это оптимально: ни один другой онлайн-алгоритм не сможет достичь лучшей производительности. [11] Однако, если ребра поступают в случайном порядке, а входной граф имеет степень, по крайней мере, логарифмическую, то можно достичь меньших коэффициентов конкуренции. [12]
Несколько авторов сделали предположения, которые подразумевают, что дробный хроматический индекс любого мультиграфа (число, которое можно вычислить за полиномиальное время с помощью линейного программирования ) находится в пределах одного хроматического индекса. [13] Если эти гипотезы верны, можно было бы вычислить число, которое никогда не отличается от хроматического индекса более чем на единицу в случае мультиграфа, что соответствует тому, что известно из теоремы Визинга для простых графов. Хотя эти гипотезы в целом и не доказаны, они, как известно, верны, когда хроматический индекс равен по крайней мере , что может случиться для мультиграфов с достаточно большой кратностью. [14]
Проверить, может ли граф быть раскрашен в один или два цвета, несложно, поэтому первый нетривиальный случай раскраски ребер — это проверка того, имеет ли граф трехцветную раскраску. Как показал Ковалик (2009), можно проверить, имеет ли граф 3-реберную раскраску за время O(1,344 n ) , используя только полиномиальное пространство. Хотя эта временная граница является экспоненциальной, она значительно быстрее, чем перебор всех возможных присвоений цветов краям. Любой двусвязный 3-регулярный граф с n вершинами имеет O(2 n /2 ) 3-раскрасок ребер; все это можно перечислить за время O(2 n /2 ) (несколько медленнее, чем время нахождения одной раскраски); как заметил Грег Куперберг , график призмы над n / 2 -сторонним многоугольником имеет раскраску Ω(2 n /2 ) (нижнюю вместо верхней границы), что показывает, что эта граница точна. [15]
Применяя точные алгоритмы раскраски вершин к линейному графу входного графа, можно оптимально раскрасить ребра любого графа с m ребрами, независимо от количества необходимых цветов, за время 2 m m O(1) и экспоненциальное пространство. или во времени O(2,2461 м ) и только в полиномиальном пространстве (Björklund, Husfeldt & Koivisto 2009).
Поскольку раскраска краев является NP-полной даже для трех цветов, маловероятно, что она будет фиксированным параметром, управляемым при параметризации количеством цветов. Однако это приемлемо по другим параметрам. В частности, Чжоу, Накано и Нишизеки (1996) показали, что для графов с шириной дерева w оптимальная раскраска ребер может быть вычислена за время O( nw (6 w ) w ( w + 1)/2 ) , граница, которая зависит суперэкспоненциально от w , но только линейно от числа n вершин графа.
Немхаузер и Парк (1991) сформулировали задачу раскраски ребер в виде целочисленной программы и описали свой опыт использования решателя целочисленного программирования для определения цветных графов ребер. Однако они не проводили никакого анализа сложности своего алгоритма.
Граф однозначно раскрашивается по k -ребрам, если существует только один способ разбить ребра на k классов цветов, игнорируя k ! возможные перестановки цветов. Для k ≠ 3 единственными графами, которые можно однозначно раскрасить по k -ребра, являются пути, циклы и звезды , но для k = 3 другие графы также могут быть однозначно раскрашиваемы по k -ребрам. Каждый граф, однозначно раскрашиваемый в 3 ребра, имеет ровно три гамильтоновых цикла (образующихся путем удаления одного из трех классов цветов), но существуют 3-регулярные графы, которые имеют три гамильтоновых цикла и не являются однозначно 3-раскрашиваемыми, например обобщенные графы Петерсена. G (6 n + 3, 2) для n ≥ 2 . Единственный известный непланарный граф, однозначно раскрашиваемый в 3 цвета, — это обобщенный граф Петерсена G (9,2) , и было высказано предположение, что других не существует. [16]
Фолкман и Фулкерсон (1969) исследовали невозрастающие последовательности чисел 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 в цепочке Кемпе , максимальном пути ребер, которые чередуются между двумя цветами. В частности, любой граф имеет справедливую раскраску ребер - раскраску ребер с оптимальным количеством цветов, в которой каждые два цветовых класса отличаются по размеру не более чем на одну единицу.
Теорема Де Брейна-Эрдеша может использоваться для переноса многих свойств раскраски ребер конечных графов на бесконечные графы . Например, теоремы Шеннона и Визинга, связывающие степень графа с его хроматическим индексом, напрямую обобщаются на бесконечные графы. [17]
Рихтер (2011) рассматривает проблему поиска рисунка данного кубического графа со свойствами, при которых все ребра рисунка имеют один из трех разных наклонов и что никакие два ребра не лежат на одной прямой друг с другом. Если такой рисунок существует, то, очевидно, наклоны ребер можно использовать в качестве цветов при 3-реберной раскраске графа. Например, изображение графа полезности K 3,3 в виде ребер и длинных диагоналей правильного шестиугольника таким образом представляет собой 3-реберную раскраску графа. Как показывает Рихтер, 3-регулярный простой двудольный граф с заданной раскраской Тейта имеет рисунок этого типа, который представляет заданную раскраску тогда и только тогда, когда граф 3-реберно-связен . Для недвудольного графа условие несколько сложнее: заданную раскраску можно изобразить рисунком, если двудольное двойное покрытие графа 3-реберно-связно и если удаление любой одноцветной пары ребер приводит к подграф, который все еще не двудольный. Все эти условия можно легко проверить за полиномиальное время; однако проблема проверки того, имеет ли 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 ) соответствует оценке, данной теоремой Визинга. [18]
Число Туэ графа — это количество цветов, необходимое для раскраски ребер, отвечающее более строгому требованию, согласно которому на каждом пути четной длины первая и вторая половины пути образуют разные последовательности цветов.
Древовидность графа — это минимальное количество цветов, необходимое для того, чтобы ребра каждого цвета не имели циклов (вместо того, чтобы в стандартной задаче раскраски ребер не было соседних пар ребер) . То есть это минимальное количество лесов , на которые можно разбить ребра графа. [19] В отличие от хроматического индекса, древесность графа может быть вычислена за полиномиальное время. [20]
Раскраска ребер списка — это задача, в которой дан граф, в котором каждое ребро связано со списком цветов, и он должен найти подходящую раскраску ребер, в которой цвет каждого ребра выбирается из списка этого ребра. Списочный хроматический индекс графа G — это наименьшее число k , обладающее тем свойством, что независимо от того, как выбираются списки цветов для ребер, если каждое ребро имеет в своем списке не менее k цветов, то раскраска гарантированно будет быть возможным. Таким образом, хроматический индекс списка всегда не меньше хроматического индекса. Гипотезу Диница о пополнении частичных латинских квадратов можно перефразировать как утверждение, что хроматическое число ребра списка полного двудольного графа K n,n равно его хроматическому числу ребра n . Гэлвин (1995) разрешил эту гипотезу, доказав в более общем плане, что в каждом двудольном графе хроматический индекс и хроматический индекс списка равны. Было высказано предположение, что равенство между хроматическим индексом и хроматическим индексом списка справедливо, даже в более общем смысле, для произвольных мультиграфов без петель; эта гипотеза остается открытой.
Многие другие широко изучаемые варианты раскраски вершин также были распространены на раскраску ребер. Например, полная раскраска ребер — это вариант полной раскраски ребер , правильная раскраска ребер, в которой каждая пара цветов должна быть представлена хотя бы одной парой соседних ребер и цель которой — максимизировать общее количество цветов. . [21] Сильная раскраска ребер — это вариант сильной раскраски ребер , раскраска ребер, в которой каждые два ребра со смежными конечными точками должны иметь разные цвета. [22] Сильная окраска границ находит применение в схемах распределения каналов для беспроводных сетей . [23]
Ациклическая раскраска ребер — это вариант ациклической раскраски ребер , раскраска ребер, для которой каждые два цветовых класса образуют ациклический подграф (то есть лес). [24] Ациклический хроматический индекс графа , обозначаемый , представляет собой наименьшее количество цветов, необходимых для правильной ациклической раскраски ребер . Было высказано предположение, что , где - максимальная степень . [25] В настоящее время наиболее известной границей является . [26] Проблема становится проще, если у него большой обхват . Точнее, существует такая константа, что если обхват не менее , то . [27] Аналогичный результат состоит в том, что для всех существует такое, что если имеет обхват не менее , то . [28]
Эппштейн (2013) изучал 3-рёберную раскраску кубических графов с дополнительным свойством, заключающимся в том, что никакие два бихроматических цикла не имеют общего друг с другом более чем одним ребром. Он показал, что существование такой раскраски эквивалентно существованию рисунка графа на трехмерной целочисленной сетке с ребрами, параллельными осям координат, и каждой параллельной оси линией, содержащей не более двух вершин. Однако, как и в стандартной задаче о раскраске трех ребер, нахождение раскраски этого типа является NP-полным.
Полная раскраска — это форма раскраски, которая сочетает в себе раскраску вершин и ребер, требуя раскрашивания как вершин, так и ребер. Любая инцидентная пара вершины и ребра или ребра и ребра должна иметь разные цвета, как и любые две соседние вершины. Было высказано предположение (объединяющее теорему Визинга и теорему Брукса ), что любой граф имеет полную раскраску, в которой количество цветов не превышает максимальной степени плюс два, но это остается недоказанным.
Если 3-регулярный граф на поверхности раскрашен в 3 цвета, его двойственный граф образует триангуляцию поверхности, которая также окрашена в цвет ребра (хотя, как правило, не имеет правильного цвета ребра) таким образом, что каждый треугольник имеет один край каждого цвета. Другие раскраски и ориентации триангуляции с другими локальными ограничениями на расположение цветов в вершинах или гранях триангуляции могут использоваться для кодирования нескольких типов геометрических объектов. Например, прямоугольные подразделения (разделения прямоугольного подразделения на меньшие прямоугольники, с тремя прямоугольниками, встречающимися в каждой вершине) могут быть описаны комбинаторно с помощью «регулярной маркировки», двухцветной раскраски ребер триангуляции, двойственной подразделению, с ограничение, заключающееся в том, что ребра, инцидентные каждой вершине, образуют четыре смежные подпоследовательности, внутри каждой из которых цвета одинаковы. Эта маркировка двойственна раскраске самого прямоугольного подразделения, в котором вертикальные края имеют один цвет, а горизонтальные края - другой цвет. Подобные локальные ограничения на порядок, в котором цветные ребра могут появляться вокруг вершины, также могут использоваться для кодирования вложений в прямолинейную сетку плоских графов и трехмерных многогранников со сторонами, параллельными осям. Для каждого из этих трех типов регулярных разметок набор правильных разметок фиксированного графа образует дистрибутивную решетку, которую можно использовать для быстрого составления списка всех геометрических структур, основанных на одном и том же графе (например, всех многогранников, параллельных осям и имеющих одинаковый скелет). ) или найти структуры, удовлетворяющие дополнительным ограничениям. [29]
Детерминированный конечный автомат можно интерпретировать как ориентированный граф , в котором каждая вершина имеет одинаковую исходящую степень d и в котором ребра окрашены в d -цвет таким образом, что каждые два ребра с одной и той же исходной вершиной имеют разные цвета. Задача раскраски дорог — это задача раскраски ребер ориентированного графа с равномерными исходящими степенями таким образом, чтобы у результирующего автомата было синхронизирующее слово . Трахтман (2009) решил проблему раскраски дорог, доказав, что такая раскраска может быть найдена всякий раз, когда данный граф сильно связен и апериодичен .
Теорема Рэмси касается проблемы k -раскраски ребер большого полного графа K n во избежание создания монохроматических полных подграфов K s некоторого заданного размера s . Согласно теореме существует число Rk ( s ) такое, что всякий раз, когда n ≥ R ( s ) , такая раскраска невозможна . Например, R 2 (3) = 6 , то есть если ребра графа K 6 двухцветные, всегда будет одноцветный треугольник.
Путь в графе с раскрашенными ребрами называется радужным путем, если ни один цвет на нем не повторяется. Граф называется радужным, если между любыми двумя парами вершин существует радужный путь. Раскраска ребер графа G цветами 1. . . t — интервальная t-раскраска, если используются все цвета, а цвета ребер, инцидентных каждой вершине графа G, различны и образуют интервал целых чисел.
Раскраска ребер полных графов может использоваться для планирования кругового турнира на как можно меньшее количество раундов, чтобы каждая пара участников играла друг с другом в одном из раундов; в этом приложении вершины графа соответствуют участникам турнира, ребра соответствуют играм, а цвета ребер соответствуют раундам, в которых проводятся игры. [30] Подобные методы раскрашивания можно также использовать для составления расписания других спортивных пар, которые не являются «все играют все»; например, в Национальной футбольной лиге пары команд, которые будут играть друг с другом в данном году, определяются на основе рекордов команд за предыдущий год, а затем к графу, сформированному с помощью алгоритма раскраски ребер, применяется алгоритм набор пар для распределения игр по выходным, в которые они проводятся. [31] Для этого приложения теорема Визинга подразумевает, что независимо от того, какой набор пар выбран (до тех пор, пока ни одна команда не играет друг с другом дважды в одном сезоне), всегда можно найти график, в котором используется максимум еще один уик-энд. чем количество игр на команду.
Планирование цеха — это задача планирования производственных процессов , в которой имеется набор объектов, подлежащих изготовлению, каждый объект имеет набор задач, которые необходимо выполнить на нем (в любом порядке), и каждое задание должно выполняться на конкретном этапе. машине, предотвращая одновременное выполнение любой другой задачи, требующей той же машины. Если все задачи имеют одинаковую длину, то эту задачу можно формализовать как задачу раскраски ребер двудольного мультиграфа, в котором вершины на одной стороне двудольного разделения представляют объекты, которые необходимо изготовить, а вершины на другой стороне двудольного разделения представляют собой производственные машины, края обозначают задачи, которые необходимо выполнить, а цвета обозначают временные этапы, в течение которых может быть выполнена каждая задача. Поскольку двусторонняя окраска ребер может выполняться за полиномиальное время, то же самое справедливо и для этого ограниченного случая планирования открытого цеха. [32]
Гандхам, Даванде и Пракаш (2005) изучают проблему планирования каналов для протоколов связи сетей множественного доступа с временным разделением каналов в сенсорных сетях как вариант раскраски границ. В этой задаче необходимо выбрать временные интервалы для границ сети беспроводной связи так, чтобы каждый узел сети мог обмениваться данными с каждым соседним узлом без помех. Использование яркой окраски краев (и использование двух временных интервалов для каждого цвета края, по одному для каждого направления) могло бы решить проблему, но может использовать больше временных интервалов, чем необходимо. Вместо этого они ищут раскраску ориентированного графа, образованного удвоением каждого неориентированного ребра сети, со свойством, что каждое направленное ребро uv имеет цвет, отличный от ребер, выходящих из v и соседей v . Они предлагают эвристику для решения этой проблемы, основанную на распределенном алгоритме (Δ + 1) -раскраски ребер вместе с фазой постобработки, которая перепланирует ребра, которые могут мешать друг другу.
В волоконно-оптической связи задача раскраски путей — это задача назначения цветов (частот света) парам узлов, желающих взаимодействовать друг с другом, и путей через волоконно-оптическую сеть связи для каждой пары с учетом ограничения что никакие два пути, которые используют один и тот же сегмент волокна, не используют одну и ту же частоту. Пути, проходящие через один и тот же коммутатор связи, но не через какой-либо сегмент волокна, могут использовать одну и ту же частоту. Когда сеть связи организована в виде звездообразной сети с одним центральным коммутатором, соединенным отдельными волокнами с каждым из узлов, задача раскраски пути может быть смоделирована точно так же, как задача раскраски ребер графа или мультиграфа, в которой соединяющиеся узлы формируют вершины графа, пары узлов, которые хотят взаимодействовать, образуют ребра графа, а частоты, которые можно использовать для каждой пары, формируют цвета задачи раскраски ребер. Для сетей связи с более общей древовидной топологией решения по раскраске локальных путей для звездообразных сетей, определенных каждым коммутатором в сети, могут быть объединены вместе, чтобы сформировать единое глобальное решение. [33]
Дженсен и Тофт (1995) перечисляют 23 открытые проблемы, касающиеся окраски краев. Они включают:
