Раскраска краев - Википедия - Edge coloring

3-краевая раскраска График дезарга.

В теория графов, окраска края из график - это присвоение «цветов» ребрам графа так, чтобы никакие два инцидентных ребра не имели одинаковый цвет. Например, на рисунке справа показана окраска ребер графа в красный, синий и зеленый цвета. Окраска краев - это один из нескольких различных типов раскраска графика. В проблема окраски краев спрашивает, можно ли раскрасить края данного графа, используя не более k разных цветов, для данного значения k, или с наименьшим возможным количеством цветов. Минимальное необходимое количество цветов для ребер данного графа называется хроматический индекс графа. Например, края графа на иллюстрации могут быть окрашены в три цвета, но не могут быть окрашены в два цвета, поэтому показанный граф имеет хроматический индекс три.

К Теорема Визинга, количество цветов, необходимых для окраски ребер простого графа, равно максимальному степень Δ или же Δ + 1. Для некоторых графиков, например двудольные графы и высокой степени планарные графы, количество цветов всегда Δ, и для мультиграфы, количество цветов может достигать 3Δ / 2. Существуют алгоритмы с полиномиальным временем, которые строят оптимальные раскраски двудольных графов, и раскраски недвудольных простых графов, которые используют не более Δ + 1 цвета; однако общая проблема поиска оптимальной раскраски ребер такова: NP-жесткий и самые быстрые известные алгоритмы для этого занимают экспоненциальное время. Было изучено множество вариантов задачи раскраски ребер, в которой присвоение цветов ребрам должно удовлетворять иным условиям, кроме несмежности. Цвета краев применяются в задачах планирования и в частотном назначении для оптоволокно сети.

Примеры

А график цикла может иметь края, окрашенные в два цвета, если длина цикла четная: просто чередуйте два цвета вокруг цикла. Однако, если длина нечетная, необходимы три цвета.^[1]

Геометрическое построение 7-краевой раскраски полный график K₈. Каждый из семи цветовых классов имеет одно ребро от центра до вершины многоугольника и три ребра, перпендикулярных к нему.

А полный график K_п с п вершины красятся с помощью п − 1 цвета, когда п - четное число; это частный случай Теорема Бараньяи. Сойфер (2008) в этом случае обеспечивает следующее геометрическое построение раскраски: место п указывает на вершины и центр регулярного (п − 1)-сторонний многоугольник. Для каждого цветового класса включите одно ребро от центра до одной из вершин многоугольника и все перпендикулярные ребра, соединяющие пары вершин многоугольника. Однако когда п странно, п нужны цвета: каждый цвет можно использовать только для (п − 1)/2 края, а 1/п доля от общей суммы.^[2]

Несколько авторов исследовали окраску краев нечетные графики, п-регулярные графы, в которых вершины представляют команды п − 1 игроков, выбранных из пула 2п − 1 игроков, и в которых края представляют возможные пары этих команд (с одним игроком, оставшимся в качестве «лишнего», чтобы судить игру). Дело, что п = 3 дает известные Граф Петерсена. В качестве Биггс (1972) объясняет проблему (для п = 6), игроки хотят найти расписание для этих пар, чтобы каждая команда играла каждую из своих шести игр в разные дни недели, с выходными для всех команд по воскресеньям; то есть, формализовав проблему математически, они хотят найти 6-краевую раскраску 6-регулярного нечетного графа О₆. Когда п 3, 4 или 8, окраска ребер О_п требует п + 1 цветов, но когда это 5, 6 или 7, только п нужны цвета.^[3]

Определения

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

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

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

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

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

А соответствие в графике грамм - набор ребер, никакие два из которых не являются смежными; а идеальное соответствие паросочетание, которое включает ребра, соприкасающиеся со всеми вершинами графа, и максимальное соответствие - это соответствие, которое включает как можно больше ребер. В раскраске ребер набор ребер любого одного цвета не должен быть смежным друг с другом, поэтому они образуют соответствие. То есть правильная раскраска ребер - это то же самое, что разбиение графа на непересекающиеся сопоставления.

Если размер максимального сопоставления в данном графе невелик, тогда потребуется много сопоставлений, чтобы покрыть все ребра графа. Выражаясь более формально, это рассуждение подразумевает, что если граф имеет м ребер всего, и если не больше β ребра могут принадлежать максимальному паросочетанию, тогда каждая раскраска ребер графа должна использовать не менее м/ β различные цвета.^[4] Например, планарный граф с 16 вершинами, показанный на иллюстрации, имеет м = 24 края. На этом графике не может быть идеального соответствия; поскольку, если центральная вершина совпадает, оставшиеся несовпадающие вершины могут быть сгруппированы в три различных связных компонента с четырьмя, пятью и пятью вершинами, а компоненты с нечетным числом вершин не могут быть полностью согласованы. Однако у графа есть максимум паросочетаний с семью ребрами, поэтому β = 7. Следовательно, количество цветов, необходимых для окраски краев графа, составляет не менее 24/7, а поскольку количество цветов должно быть целым числом, оно должно быть не менее четырех.

Для регулярный граф степени k который не имеет идеального соответствия, эта нижняя граница может использоваться, чтобы показать, что по крайней мере k + 1 нужны цвета.^[4] В частности, это верно для регулярного графа с нечетным числом вершин (например, для нечетных полных графов); для таких графов лемма о рукопожатии, k сам должен быть четным. Однако неравенство χ ′ ≥ м/ β не полностью объясняет хроматический индекс каждого регулярного графа, потому что есть регулярные графы, которые имеют идеальное соответствие, но не являются k- крашеный. Например, Граф Петерсена регулярно, с м = 15 и с β = 5 края в его идеальном соответствии, но у него нет 3-краевой окраски.

Отношение к степени

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

Хроматическое число ребер графа грамм очень тесно связан с максимальная степень Δ (грамм), наибольшее количество ребер, инцидентных любой единственной вершине грамм. Четко, χ ′ (грамм) ≥ Δ (грамм), если Δ разные ребра встречаются в одной вершине v, то всем этим ребрам нужно присвоить разные цвета друг от друга, а это возможно только при наличии как минимум Δ цвета, доступные для назначения. Теорема Визинга (назван в честь Вадим Геннадьевич Визинг опубликовавший его в 1964 г.) утверждает, что эта граница почти точная: для любого графа хроматическое число ребер равно Δ (грамм) или же Δ (грамм) + 1.Когда χ ′ (грамм) = Δ (грамм), грамм относится к классу 1; в противном случае говорят, что он принадлежит к классу 2.

Каждый двудольный граф относится к классу 1,^[5] и почти все случайные графы относятся к классу 1.^[6] Однако это НП-полный чтобы определить, принадлежит ли произвольный граф к классу 1.^[7]

Визинг (1965) доказал, что планарные графы максимальной степени по крайней мере восемь относятся к классу один и предполагают, что то же самое верно и для плоских графов максимальной степени семь или шесть. С другой стороны, существуют планарные графы максимальной степени от второго до пятого, относящиеся ко второму классу. Гипотеза с тех пор была доказана для графов максимальной степени семь.^[8] Без моста планарный кубические графы все относятся к классу 1; это эквивалентная форма теорема четырех цветов.^[9]

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

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

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

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

Мультиграфы

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

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

Алгоритмы

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

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

В случае двудольные графы или мультиграфы с максимальной степенью Δ, оптимальное количество цветов ровно Δ. Коул, Ост и Ширра (2001) показал, что оптимальная окраска ребер этих графов может быть найдена в приближении к линейной оценке времени O (м журнал Δ), куда м - количество ребер в графе; более простые, но несколько медленные алгоритмы описываются Коул и Хопкрофт (1982) и Алон (2003). Алгоритм Алон (2003) начинается с того, что входной граф становится регулярным, без увеличения его степени или значительного увеличения размера, путем объединения пар вершин, принадлежащих одной стороне двудольного деления, а затем добавления небольшого количества дополнительных вершин и ребер. Затем, если степень нечетная, Алон находит единственное идеальное соответствие за почти линейное время, присваивает ему цвет и удаляет его с графика, в результате чего степень становится четной. Наконец, Алон применяет наблюдение Габоу (1976), который выбирает чередующиеся подмножества ребер в Эйлер тур графа разбивает его на два регулярных подграфа, чтобы разбить задачу раскраски ребер на две меньшие подзадачи, и его алгоритм решает две подзадачи рекурсивно. Общее время для его алгоритма составляет O (м бревно м).

За планарные графы с максимальной степенью Δ ≥ 7, оптимальное количество цветов снова точно Δ. При более сильном предположении, что Δ ≥ 9, можно найти оптимальную раскраску ребер за линейное время (Коул и Ковалик, 2008 ).

Для d-регулярных графов, которые являются псевдослучайными в том смысле, что их матрица смежности имеет второе наибольшее собственное значение (по модулю) не более d^1-е, d - оптимальное количество цветов (Фербер и Джейн 2018 ).

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

Мисра и Грис (1992) и Gabow et al. (1985) описать алгоритмы полиномиального времени для раскраски любого графа с Δ + 1 цвета, удовлетворяющие оценке теоремы Визинга; видеть Алгоритм раскраски краев Misra & Gries.

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

А жадная окраска алгоритм, который рассматривает ребра графа или мультиграфа одно за другим, присваивая каждому ребру первый доступный цвет, иногда может использоваться до 2Δ - 1 цветов, что может быть почти в два раза больше цветов, чем необходимо. Однако его преимущество заключается в том, что его можно использовать в онлайн алгоритм настройка, при которой входной граф заранее не известен; в этой обстановке его конкурентное соотношение равно двум, и это оптимально: ни один другой онлайн-алгоритм не может обеспечить лучшую производительность.^[11] Однако, если ребра прибывают в случайном порядке, а входной граф имеет степень, по крайней мере, логарифмическую, тогда можно достичь меньших конкурентных соотношений.^[12]

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

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

Проверить, может ли граф быть краской, окрашенной в один или два цвета, несложно, поэтому первый нетривиальный случай окраски краев - это проверка того, имеет ли граф трехкратную окраску. Ковалик (2009) показал, что можно проверить, имеет ли граф 3-краевую раскраску во времени О (1,344^п), используя только полиномиальное пространство. Хотя эта временная граница экспоненциальна, она значительно быстрее, чем перебор всех возможных присвоений цветов краям. Каждый двусвязный 3-регулярный граф с п вершины O (2^п/2) 3-краевые раскраски; все это можно перечислить вовремя O (2^п/2) (несколько медленнее, чем время на поиск единственной окраски); в качестве Грег Куперберг наблюдается, график призма над п/2-сторонний многоугольник имеет Ом (2^п/2) раскраски (нижняя, а не верхняя граница), показывающие, что эта граница жесткая.^[15]

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

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

Немхаузер и Парк (1991) сформулировать задачу раскраски краев как целочисленная программа и описать свой опыт использования решателя целочисленного программирования для краевых цветных графов. Однако они не проводили анализ сложности своего алгоритма.

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

Уникальный трехцветный обобщенный граф Петерсена грамм(9,2). Один из трех его цветовых классов показан светлыми краями, а два других можно найти либо путем поворота светлых краев на 40 ° в каждом направлении, либо путем разделения темного гамильтонова цикла на чередующиеся края.

График однозначно k-рёбра-раскрашиваем, если есть только один способ разбить края на k цветовые классы, игнорируя k! возможные перестановки цветов. За k ≠ 3, единственное уникальное k-ребро раскрашиваемые графы - это пути, циклы и звезды, но для k = 3 другие графы также могут быть однозначно k- крашеный. Каждый граф с уникальной 3-краской Гамильтоновы циклы (образованный удалением одного из трех цветовых классов), но существуют 3-регулярные графы, которые имеют три гамильтоновых цикла и не являются однозначно 3-раскрашиваемыми, например обобщенные графы Петерсена грамм(6п + 3, 2) за п ≥ 2. Единственным известным непланарным однозначно 3-раскрашиваемым графом является обобщенный граф Петерсена грамм(9,2), и было высказано предположение, что других не существует.^[16]

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

Фолкман и Фулкерсон (1969) исследовали невозрастающие последовательности чисел м₁, м₂, м₃, ... со свойством, что существует правильная раскраска ребер данного графа грамм с м₁ края первого цвета, м₂ края второго цвета и т. д. Они заметили, что если последовательность п возможно в этом смысле и больше в лексикографический порядок чем последовательность Q на ту же сумму, то Q тоже возможно. Ведь если п > Q в лексикографическом порядке, то п может быть преобразован в Q последовательностью шагов, каждый из которых уменьшает одно из чисел м_я на одну единицу и увеличивает другое более позднее число м_j с я < j на одну единицу. Что касается окраски краев, начиная с окраски, которая реализует п, каждый из этих шагов может быть выполнен заменой цветов я и j на Кемпе цепь, максимальный путь ребер, чередующихся двух цветов. В частности, любой граф имеет справедливый окраска краев, окраска краев с оптимальным количеством цветов, при котором каждые два цветовых класса отличаются размером не более чем на одну единицу.

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

Рихтер (2011) рассматривает проблему поиска рисунок графика данного кубический граф со свойствами, что все кромки на чертеже имеют один из трех разных уклонов и что никакие две кромки не лежат на одной линии друг с другом. Если такой рисунок существует, то очевидно, что наклоны ребер могут использоваться как цвета в раскраске трех ребер графа. Например, рисунок график полезности K_3,3 как края и длинные диагонали правильный шестиугольник представляет собой 3-краевую раскраску графа таким образом. Как показывает Рихтер, 3-регулярный простой двудольный граф с заданной раскраской Тейта имеет рисунок этого типа, который представляет данную раскраску тогда и только тогда, когда граф 3-х стороннее соединение. Для недвудольного графа условие немного сложнее: данная раскраска может быть представлена ​​рисунком, если двусторонняя двойная обложка графа является 3-реберно связным, и если удаление любой одноцветной пары ребер приводит к подграфу, который по-прежнему не является двудольным. Все эти условия можно легко проверить за полиномиальное время; тем не менее, проблема проверки того, имеет ли четырехмерный регулярный граф с 4-мя краями рисунок с ребрами с четырьмя наклонами, представляющими цвета наклонами, является полной для экзистенциальная теория реальности, класс сложности не менее сложный, чем NP-полный.

Хроматический индекс не только связан с максимальной степенью и максимальным числом совпадений графа, но и с линейная древовидность ля (грамм) графа грамм, минимальное количество линейных лесов (непересекающихся объединений путей), на которые могут быть разбиты ребра графа. Сопоставление - это особый вид линейного леса, и, с другой стороны, любой линейный лес может быть двухреберным, поэтому для каждого грамм следует, что ля (грамм) ≤ χ ′ (грамм) ≤ 2 la (грамм). Гипотеза Акиямы (назван в честь Джин Акияма ) утверждает, что ${ Displaystyle mathop { mathrm {la}} (G) leq left lceil { frac { Delta +1} {2}} right rceil}$, из которого более строго следовало бы, что 2 ля (грамм) - 2 ≤ χ ′ (грамм) ≤ 2 la (грамм). Для графиков максимальной степени три, ля (грамм) всегда ровно два, поэтому в этом случае оценка χ ′ (грамм) ≤ 2 la (грамм) соответствует оценке, данной теоремой Визинга.^[18]

Другие типы

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

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

В родословие графа - это минимальное количество цветов, необходимое для того, чтобы у ребер каждого цвета не было циклов (вместо того, чтобы в стандартной задаче раскраски ребер не было смежных пар ребер). То есть это минимальное количество леса на которые можно разбить ребра графа.^[19] В отличие от хроматического индекса, древовидность графа может быть вычислена за полиномиальное время.^[20]

Раскраска по краям списка - это проблема, в которой каждому дается граф, в котором каждое ребро связано со списком цветов, и необходимо найти правильную окраску ребер, в которой цвет каждого ребра берется из этого списка ребер. Список хроматического индекса графа грамм это наименьшее число k с тем свойством, что независимо от того, как вы выбираете списки цветов для ребер, если каждое ребро имеет по крайней мере k цветов в своем списке, то раскраска гарантированно возможна. Таким образом, хроматический индекс списка всегда по крайней мере равен хроматическому индексу. В Гипотеза диница по завершении частичного Латинские квадраты можно перефразировать как утверждение, что хроматическое число края списка полный двудольный граф K_{п, п} равно его краевому хроматическому числу,п. Гэлвин (1995) разрешил эту гипотезу, доказав, в более общем смысле, что в каждом двудольном графе хроматический индекс и хроматический индекс списка равны. Предполагается, что равенство между хроматическим индексом и хроматическим индексом списка справедливо, даже в более общем смысле, для произвольных мультиграфов без петель; эта гипотеза остается открытой.

Многие другие обычно изучаемые варианты раскраски вершин также были распространены на раскраски ребер. Например, полная раскраска ребер - это вариант раскраски ребер полная окраска - правильная окраска краев, в которой каждая пара цветов должна быть представлена ​​по крайней мере одной парой смежных краев и цель которой - максимизировать общее количество цветов.^[21] Сильная окраска кромок - это вариант окраски кромок сильная окраска, окраска ребер, при которой каждые два ребра со смежными конечными точками должны иметь разные цвета.^[22] Сильная окраска кромок находит применение в схемы распределения каналов за беспроводные сети.^[23]

Ациклическая окраска ребер - это вариант окраски ребер ациклическая окраска, окраска ребер, для которой каждые два цветовых класса образуют ациклический подграф (то есть лес).^[24] Ациклический хроматический индекс графа ${ displaystyle G}$, обозначаемый ${ displaystyle a '(G)}$, - наименьшее количество цветов, необходимое для правильной ациклической окраски ребер ${ displaystyle G}$. Было высказано предположение, что ${ Displaystyle а '(G) leq Delta +2}$, куда ${ displaystyle Delta}$ это максимальная степень ${ displaystyle G}$.^[25] В настоящее время наиболее известная граница ${ Displaystyle а '(G) leq lceil 3.74 ( Delta -1) rceil}$.^[26] Проблема становится проще, когда ${ displaystyle G}$ имеет большой обхват. В частности, существует постоянная ${ displaystyle c}$ такой, что если обхват ${ displaystyle G}$ по крайней мере ${ displaystyle c Delta log Delta}$, тогда ${ Displaystyle а '(G) leq Delta +2}$.^[27] Аналогичный результат для всех ${ displaystyle epsilon> 0}$ существует ${ displaystyle g}$ так что если ${ displaystyle G}$ имеет обхват как минимум ${ displaystyle g}$, тогда ${ Displaystyle а '(G) leq (1+ epsilon) Delta}$.^[28]

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

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

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

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

Теорема Рамсея касается проблемы k-крашивание краев большого полный график K_п во избежание создания монохроматических полных подграфов K_s некоторого заданного размераs. Согласно теореме существует число р_k(s) так что всякий раз, когда п ≥ р(s), такая окраска невозможна. Например, р₂(3) = 6, то есть если ребра графа K₆ двухцветные, всегда будет однотонный треугольник.

Путь в графе с краской краев называется радуга путь, если на нем не повторяется ни один цвет. Граф называется радужным, если между любыми двумя парами вершин существует радужный путь. Раскраска ребер графа G в цвета 1.. . это интервал t раскраска если используются все цвета и цвета ребер, инцидентных каждой вершине графа G, различны и образуют интервал целых чисел.

Приложения

Раскраски краев полных графов можно использовать для планирования круговой турнир на как можно меньше раундов, чтобы каждая пара участников играла друг с другом в одном из раундов; в этом приложении вершины графа соответствуют участникам турнира, ребра соответствуют играм, а цвета ребер соответствуют раундам, в которых проводятся игры.^[30] Подобные техники раскраски также могут использоваться для планирования других спортивных пар, которые не являются универсальными; например, в Национальная футбольная лига, пары команд, которые будут играть друг с другом в данном году, определяются на основе записей команд за предыдущий год, а затем алгоритм окраски ребер применяется к графу, сформированному набором пар, чтобы назначить игры в выходные, в которые они играют.^[31] Для этого приложения теорема Визинга подразумевает, что независимо от того, какой набор пар выбран (до тех пор, пока ни одна из команд не играет друг с другом дважды в одном сезоне), всегда можно найти расписание, которое использует как минимум на один уик-энд больше, чем есть игры на команду.

Планирование открытия магазина это проблема планирование производственных процессов, в котором есть набор объектов для производства, каждый объект имеет набор задач, которые должны быть выполнены на нем (в любом порядке), и каждая задача должна выполняться на определенной машине, предотвращая любые другие задачи, требующие того же машина из выполняемого одновременно. Если все задачи имеют одинаковую длину, то эту задачу можно формализовать как задачу раскраски ребер двудольного мультиграфа, в котором вершины на одной стороне двудольного графа представляют объекты, которые должны быть изготовлены, а вершины на другой стороне двудольного графа представляют На производственных машинах края представляют задачи, которые должны быть выполнены, а цвета представляют собой временные шаги, за которые может быть выполнена каждая задача. Поскольку двудольная окраска краев может выполняться за полиномиальное время, то же самое верно и для этого ограниченного случая планирования открытого магазина.^[32]

Гандхэм, Даванд и Пракаш (2005) изучить проблему планирования ссылок для множественный доступ с временным разделением сетевые протоколы связи на сенсорные сети как вариант окраски кромки. В этой задаче необходимо выбрать временные интервалы для границ сети беспроводной связи, чтобы каждый узел сети мог связываться с каждым соседним узлом без помех. Использование сильной окраски краев (и использование двух временных интервалов для каждого цвета краев, по одному для каждого направления) решило бы проблему, но могло бы использовать больше временных интервалов, чем необходимо. Вместо этого они ищут окраску ориентированного графа, образованного удвоением каждого неориентированного ребра сети, с тем свойством, что каждое направленное ребро УФ имеет другой цвет по сравнению с краями, выходящими из v и от соседей v. Они предлагают эвристику для этой проблемы, основанную на распределенном алгоритме для (Δ + 1)-edge-раскраска вместе с фазой постобработки, которая перепланировывает края, которые могут мешать друг другу.

В волоконно-оптическая связь, то раскраска пути проблема заключается в назначении цветов (частот света) парам узлов, которые хотят общаться друг с другом, и путей через волоконно-оптическую сеть связи для каждой пары, при условии, что никакие два пути, которые разделяют сегмент волокна используют ту же частоту, что и друг друга. Пути, которые проходят через один и тот же коммутатор связи, но не через какой-либо сегмент волокна, могут использовать одну и ту же частоту. Когда сеть связи устроена как звездная сеть, с одним центральным переключателем, соединенным отдельными волокнами с каждым из узлов, проблема раскраски пути может быть смоделирована точно как задача раскраски ребер графа или мультиграфа, в котором сообщающиеся узлы образуют вершины графа, пары узлов, которые хотят для связи с ребрами графа, а частоты, которые могут использоваться для каждой пары, образуют цвета задачи раскраски ребер. Для сетей связи с более общей древовидной топологией решения по раскраске локальных путей для звездообразных сетей, определенные каждым коммутатором в сети, могут быть объединены вместе, чтобы сформировать единое глобальное решение.^[33]

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

Дженсен и Тофт (1995) перечислим 23 открытых проблемы, касающихся раскраски ребер. Они включают:

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

Примечания

Рекомендации