Окраска кромок - Edge coloring

Трехреберная раскраска графа Дезарга

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

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

Примеры

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

Геометрическое построение 7-реберной раскраски полного графа

K 8

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мультиграфы

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

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

Алгоритмы

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

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

В случае двудольных графов или мультиграфов с максимальной степенью $Δ$ оптимальное количество цветов равно $Δ$ . Cole, Ost & Schirra (2001) показали, что оптимальную окраску ребер этих графов можно найти в почти линейной временной границе $O (m log Δ)$ , где $m$ - количество ребер в графе; более простые, но несколько более медленные алгоритмы описаны Cole & Hopcroft (1982) и Alon (2003) . Алгоритм Алона (2003) начинается с того, что входной граф становится регулярным, без увеличения его степени или значительного увеличения размера, путем слияния пар вершин, принадлежащих одной стороне двудольного разделения, а затем добавления небольшого количества дополнительных вершин и ребер. . Затем, если степень нечетная, Алон находит единственное идеальное соответствие за почти линейное время, назначает ему цвет и удаляет его с графика, в результате чего степень становится четной. Наконец, Алон применяет наблюдение Габоу (1976) , что выбор чередующихся подмножеств ребер в эйлеровом обходе графа разбивает его на два регулярных подграфа, чтобы разбить задачу раскраски ребер на две меньшие подзадачи, и его алгоритм решает две подзадачи. рекурсивно . Общее время для его алгоритма составляет $O (m log m)$ .

Для плоских графов с максимальной степенью $Δ \geq 7$ оптимальное количество цветов снова равно $Δ$ . При более сильном предположении, что $Δ \geq 9$ , можно найти оптимальную раскраску ребер за линейное время ( Cole & Kowalik 2008 ).

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

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

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

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

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

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

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

Проверить, может ли граф быть краской, окрашенной в один или два цвета, несложно, поэтому первый нетривиальный случай окраски краев - это проверка того, имеет ли граф трехкратную окраску. Как показал Ковалик (2009) , можно проверить, имеет ли граф 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 м)$ и только в полиномиальном пространстве ( Björklund, Husfeldt & Koivisto 2009 ).

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

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

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

Однозначно 3-раскрашиваемый обобщенный граф Петерсена

G (9,2)

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

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

Полный двудольный граф K _3,3 с каждым из своих цветовых классов обращаются в виде параллельных отрезков , на различных линиях.

Фолкман и Фалкерсон (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$ в цепочке Кемпе , максимальном пути ребер, которые чередуются между двумя цветами. В частности, любой граф имеет равномерную окраску ребер, раскраску ребер оптимальным количеством цветов, в которой каждые два цветовых класса отличаются по размеру не более чем на одну единицу.

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

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

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

Другие типы

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

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

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

Раскраска ребер списка - это проблема, в которой каждому дается граф, в котором каждое ребро связано со списком цветов, и он должен найти правильную окраску ребер, в которой цвет каждого ребра берется из этого списка ребер. Хроматический индекс списка графа $G$ - это наименьшее число $k$ со свойством, что независимо от того, как выбираются списки цветов для ребер, до тех пор, пока каждое ребро имеет не менее $k$ цветов в своем списке, раскраска гарантированно будет быть возможно. Таким образом, хроматический индекс списка всегда по крайней мере такой же большой, как хроматический индекс. Диницы гипотезы о завершении частичных латинских квадратов можно перефразировать как утверждение , что список края хроматического номер полного двудольного графа $K п, п$ равно ее края хроматического числа, $п$ . Галвин (1995) разрешил эту гипотезу, доказав в более общем плане, что в каждом двудольном графе хроматический индекс и хроматический индекс списка равны. Предполагается, что равенство между хроматическим индексом и хроматическим индексом списка справедливо, даже в более общем смысле, для произвольных мультиграфов без петель; эта гипотеза остается открытой.

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

Примечания

использованная литература

Акияма, Джин; Экзу, Джеффри; Харари, Франк (1980), "Покрытие и упаковка в графах. III. Циклические и ациклические инварианты", Mathematica Slovaca , 30 (4): 405–417, MR 0595302.
Алон, Нога (2003), "Простой алгоритм окраски ребер двудольных мультиграфов", Письма об обработке информации , 85 (6): 301–302, DOI : 10.1016 / S0020-0190 (02) 00446-5 , MR 1956451.
Алон, Нога ; Судаков, Бенни; Закс, Ayal (2001), "ациклические краевые раскраски графов", Журнал теории графов , 37 (3): 157-167, DOI : 10.1002 / jgt.1010 , МР 1837021.
Андерсен, Ларс Døvling (1977), "О краевых-раскрасок графов", Mathematica Scandinavica , 40 (2): 161-175, DOI : 10,7146 / math.scand.a-11685 , МР 0465922. Цитируется Chen, Yu & Zang (2011) .
Аппель, К .; Хакен, W. (1976), "Каждая плоская карта четыре раскраску", Бюллетень Американского математического общества , 82 (5): 711-712, DOI : 10,1090 / S0002-9904-1976-14122-5 , MR 0424602.
Бахмани, Бахман; Мехта, Араньяк; Мотвани, Раджив (2010), "Конкурентный онлайн-алгоритм раскраски ребер графа 1.43 в модели прибытия случайного порядка", Труды Двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '10) , стр. 31–39.
Бар-Ной, Амоц; Мотвани, Раджив ; Наор, Джозеф (1992), «Жадный алгоритм оптимален для окраски краев в режиме онлайн», Письма об обработке информации , 44 (5): 251–253, DOI : 10.1016 / 0020-0190 (92) 90209-E.
Барретт, К.Л .; Istrate, G .; Кумар, VSA; Marathe, MV; Thite, S .; Туласидасан, С. (2006), "Сильная окраска краев для назначения каналов в беспроводных радиосетях", Proc. Четвертая ежегодная международная конференция IEEE по повсеместным вычислениям и семинарам по коммуникациям (PerCom Workshops 2006) , стр. 106, DOI : 10,1109 / PERCOMW.2006.129 , ISBN 0-7695-2520-2, S2CID 5797236.
Биггс, Норман (1972), Гай, Ричард К. (ред.), "Ребро-раскраска проблема", проблемы исследования, American Mathematical Monthly , 79 (9): 1018-1020, DOI : 10,2307 / 2318076 , JSTOR 2318076.
Биггс, Норман (1979), «Некоторая странная теория графов», Вторая международная конференция по комбинаторной математике, Анналы Нью-Йоркской академии наук , 319 (1): 71–81, Bibcode : 1979NYASA.319 ... 71B , doi : 10.1111 / j.1749-6632.1979.tb32775.x , S2CID 84995087.
Бьёрклунд, Андреас; Хусфельдт, Тор; Койвисто, Микко (2009), "Установить разделение с помощью включения-исключения" (PDF) , SIAM журнал по вычислениям , 39 (2): 546-563, DOI : 10,1137 / 070683933 , MR 2529771.
Bosak, Юрай (1972), "хроматический индекс конечных и бесконечных графов", Чехословацкий математический журнал , 22 (97): 272-290, DOI : 10,21136 / CMJ.1972.101098 , МР 0309777.
Босак, Юрай; Нешетржил, Ярослав (1976), «Полные и псевдополные раскраски графа», Matematicky Časopis Slovenskej Akadémie Vied , 26 (3): 171–184, MR 0439672.
Цай, XS; Perarnau, G .; Рид, BA ; Уоттс, AB (2014), «Ациклические раскраски ребер графов с большим обхватом», Случайные структуры и алгоритмы , 50 (4): 511–533, arXiv : 1411.3047 , doi : 10.1002 / rsa.20695 , S2CID 7727097.
Burke, E .; De Werra, D .; Кингстон, Дж. (2004), «5.6.5 Спортивное расписание» , в JL, Gross; Йеллен Дж. (Ред.), Справочник по теории графов , CRC Press, стр. 462, ISBN 978-1-58488-090-5.
Чен, Гуантао; Юй Синсин; Занг, Вэнань (2011), "Аппроксимация хроматическую индекс мультиграфов", журнал комбинаторной оптимизации , 21 (2): 219-246, DOI : 10.1007 / s10878-009-9232-у , МР 2770056 , S2CID 169162.
Чудновский, Мария ; Эдвардс, Кэтрин; Сеймур, Пол (2012), " Восьмирегулярные плоские графы с окраской ребер ", arXiv : 1209.1176 [ cs.DM ].
Коул, Ричард; Hopcroft, Джон (1982), "На краю окраски двудольные графы", SIAM журнал по вычислениям , 11 (3): 540-546, DOI : 10,1137 / 0211043 , ЛВП : 1813/6283 , MR 0664720.
Коул, Ричард; Kowalik, Лукаш (2008), "Новые линейные времени алгоритмы края раскраски плоских графов", Algorithmica , 50 (3): 351-368, DOI : 10.1007 / s00453-007-9044-3 , MR 2366985 , S2CID 7692895.
Коул, Ричард; Ост, Кирстин; Ширра, Стефан (2001), "Край-раскраски двудольных мультиграфов в $O (Е журнал D)$ время", Combinatorica , 21 (1): 5-12, DOI : 10.1007 / s004930170002 , МР 1805711 , S2CID 522145.
Крэнстон, Дэниел В. (2006), «Сильная раскраска ребер графов с максимальной степенью 4 с использованием 22 цветов», Дискретная математика , 306 (21): 2772–2778, arXiv : math / 0601623 , Bibcode : 2006math .... ..1623C , DOI : 10.1016 / j.disc.2006.03.053 , МР 2264374 , S2CID 1097275.
Эпштейн, Дэвид (2013), «Сложность построения трехмерного ортогонального графа без изгибов», Журнал алгоритмов и приложений графов , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155 / jgaa.00283 , S2CID 2716392.
Эпштейн, Дэвид (2010), "Регулярные разметки и геометрические структуры", Proc. 22-я канадская конференция по вычислительной геометрии (CCCG 2010) (PDF) , Университет Манитобы, arXiv : 1007.0221 , Bibcode : 2010arXiv1007.0221E.
Эрдеш, Пол ; Уилсон, Робин Дж. (1977), «Примечание о хроматическом индексе почти всех графов» (PDF) , Журнал комбинаторной теории , серия B, 23 (2–3): 255–257, DOI : 10.1016 / 0095-8956 (77) 90039-9.
Эрлебах, Томас; Янсен, Клаус (2001), «Сложность раскраски путей и планирования вызовов», Теоретическая информатика , 255 (1-2): 33-50, DOI : 10.1016 / S0304-3975 (99) 00152-8 , MR 1819065.
Фербер, Асаф; Джайн, Вишеш (2018), «1-факторизации псевдослучайных графов», arXiv : 1803.10361 [ math.CO ].
Fiamčik, J. (1978), "Ациклический хроматический класс графа", Math. Словака , 28 : 139–145.
Fiorini, S .; Уилсон, Робин Джеймс (1977), окраска ребер графов , Research Notes in Mathematics, 16 , London: Pitman, ISBN 0-273-01129-4, Руководство по ремонту 0543798.
Фолкман, Джон ; Фулкерсон, Д. Р. (1969), "Раскраски ребер в двудольных графах", Комбинаторная математика и ее приложения (Proc. Conf., Univ. North Carolina, Chapel Hill, NC, 1967) , Chapel Hill, NC: Univ. North Carolina Press, стр. 561–577, MR 0262112.
Fouquet, J.-L .; Жоливе, Ж.-Л. (1983), "Сильные раскраски ребер графов и приложения к мульти- $k$ -угольникам", Ars Combinatoria , 16 (A): 141–150, MR 0737086..
Frieze, Алан М .; Кривелевич Михаил; Судаков, Бенни (2005), "Сильный хроматической индекс случайных графов" (PDF) , SIAM журнал по дискретной математике , 19 (3): 719-727 (электронный), DOI : 10,1137 / S0895480104445757 , MR 2191290.
Gabow, Гарольд Н. (1976), "Использование Эйлера разделов на цвет края двудольных мультиграфов", Международный журнал компьютерных и информационных наук , 5 (4): 345-355, DOI : 10.1007 / BF00998632 , MR 0422081 , S2CID 36331285.
Габоу, Гарольд Н .; Нишизеки, Такао ; Карив, Одед; Левен, Даниэль; Терада, Осаму (1985), Алгоритмы раскрашивания ребер графов , Tech. Отчет TRECIS-8501, Университет Тохоку.
Габоу, Гарольд Н .; Вестерманн, Герберт Х. (1992), "Лес, кадры и игры: алгоритмы для матроидных сумм и приложений", Algorithmica , 7 (5-6): 465-497, DOI : 10.1007 / BF01758774 , МР 1154585 , S2CID 40358357.
Гальвин, F. (1995), "Список хроматический индекс двудольного мультиграфа", Журнал комбинаторной теории , серии B, 63 (1): 153-158, DOI : 10,1006 / jctb.1995.1011.
Gandham, S .; Dawande, M .; Пракаш, Р. (2005), "Планирование каналов в сенсорных сетях: пересмотр распределенной окраски краев", Proc. 24 - й ИНФОК , 4 ., Стр 2492-2501, DOI : 10,1109 / INFCOM.2005.1498534 , ISBN 0-7803-8968-9, S2CID 8085139.
Giotis, I .; Kirousis, L .; Псаромилигкос, К.И.; Thilikos, DM (2015), "Об алгоритмической локальной лемме Ловаса и ациклической раскраске ребер", Труды Двенадцатого семинара по аналитической алгоритмике и комбинаторике (ANALCO) , стр. 16, DOI : 10,1137 / 1.9781611973761.2 , ISBN 978-1-61197-376-1.
Гольдберг, М.К. (1973), "Мультиграфы с почти максимальным хроматическим индексом", Дискрет. Анализ. (23): 3–7, 72, MR 0354429. Цитируется Chen, Yu & Zang (2011) .
Habib, M .; Перош Б. (1982), "Некоторые проблемы линейной древовидности", Дискретная математика , 41 (2): 219–220, DOI : 10.1016 / 0012-365X (82) 90209-6 , MR 0676882.
Holyer, Ян (1981), "NP-полнота края окраски", SIAM журнал по вычислениям , 10 (4): 718-720, DOI : 10,1137 / 0210055.
Хорак, Питер; Нипель, Людовит (1982), "Краткое доказательство линейной теоремы о древовидности для кубических графов", Acta Mathematica Universitatis Comenianae , 40/41: 275–277, MR 0686983.
Дженсен, Томми Р .; Тофт, Бьярн (1995), Проблемы раскраски графов , Нью-Йорк: Wiley-Interscience, ISBN 0-471-02865-7.
Карлофф, Ховард Дж .; Шмойс, Дэвид Б. (1987), «Эффективные параллельные алгоритмы для задач раскраски краев», Журнал алгоритмов , 8 (1): 39–52, DOI : 10.1016 / 0196-6774 (87) 90026-5 , MR 0875324.
Konig, Д. (1916), "Убер графена унд Ihre Anwendung Ауф Determinantentheorie унд Mengenlehre" , Mathematische Annalen , 77 (4): 453-465, DOI : 10.1007 / BF01456961 , ЛВП : 10338.dmlcz / 127635 , S2CID 121097364 , заархивированы из оригинала от 19 января 2015 г. , получено 30 сентября 2013 г..
Kowalik, Лукаш (2009), "Улучшение края окраски с тремя цветами", Теоретическая информатика , 410 (38-40): 3733-3742, DOI : 10.1016 / j.tcs.2009.05.005 , MR 2553326.
Mahdian Мохаммад (2002), "О вычислительной сложности сильных окраски краев", Дискретная прикладная математика , 118 (3): 239-248, DOI : 10.1016 / S0166-218X (01) 00237-2 , МР 1892971.
Мередит, Гай Х.Дж.; Ллойд, Э. Кейт (1973), «Футболисты Кроама», Журнал комбинаторной теории , серия B, 15 (2): 161–166, DOI : 10.1016 / 0095-8956 (73) 90016-6.
Misra, J .; Грис, Дэвид (1992), «Конструктивное доказательство теоремы Визинга», Информационные письма , 41 (3): 131–133, DOI : 10.1016 / 0020-0190 (92) 90041-S.
Мутху, Рахул; Narayanan, N .; Субраманьян, CR (2007), "Улучшенные ограничения на ациклическом краю окраски", дискретная математика , 307 (23): 3063-3069, DOI : 10.1016 / j.disc.2007.03.006 , МР 2371078.
Nash-Williams, C. St. JA (1964), "Разложение конечных графов в лесах", журнал Лондонского математического общества , вторая серия, 39 : 12, DOI : 10,1112 / jlms / s1-39.1.12 , MR 0161333
Немхаузер, Джордж Л .; Парк, Sungsoo (1991), "Полиэдральный подход к краю окраски", исследование операций Письмо , 10 (6): 315-322, DOI : 10,1016 / 0167-6377 (91) 90003-8 , МР 1128970.
Рихтер, Дэвид А. (2011), «Как нарисовать раскрашиваемый по Тэту граф», в Брандесе, Ульрик ; Cornelsen, Sabine (ред.), Proc. 18 - й Международный симпозиум по Graph Drawing (GD 2010) , Lecture Notes в области компьютерных наук, 6502 , Springer-Verlag, стр 353-364,. Дои : 10.1007 / 978-3-642-18469-7_32 , ISBN 978-3-642-18468-0.
Сандерс, Дэниел П .; Чжао, Юэ (2001), «Планарные графы максимальной степени семь относятся к классу I», Журнал комбинаторной теории , серия B, 83 (2): 201–212, DOI : 10.1006 / jctb.2001.2047.
Seymour, PD (1979), "О multicolourings кубических графов и домыслы Фулкерсон и Татты", Труды Лондонского математического общества , Третья серия, 38 (3): 423-460, DOI : 10.1112 / ПНИЛИ / s3-38.3 .423 , Руководство по ремонту 0532981.
Швенк, Аллен Дж. (1989), «Перечисление гамильтоновых циклов в некоторых обобщенных графах Петерсена», Журнал комбинаторной теории , серия B, 47 (1): 53–59, DOI : 10.1016 / 0095-8956 (89) 90064- 6 , Руководство по ремонту 1007713.
Шеннон, Клод Э. (1949), "Теорема о раскраске линий сети", J. Math. Физика , 28 (1-4): 148-151, DOI : 10.1002 / sapm1949281148 , ЛВП : 10338.dmlcz / 101098 , МР 0030203.
Skiena, Стивен С. (2008), "+16,8 реберной раскраске", Алгоритм Руководство по проектированию (2 - е изд.), Springer-Verlag, стр 548-550,. Дои : 10.1007 / 978-1-84800-070-4_16 , ISBN 978-1-84800-069-8. См. Также веб-сайт для этого раздела книги в репозитории алгоритмов Стоуни-Брук.
Сойфер, Александр (2008), Математическая книжка-раскраска , Springer-Verlag, ISBN 978-0-387-74640-1.
Tait, PG (1880), "Замечания о раскраске карт", Proc. R. Soc. Эдинбург , 10 : 729, DOI : 10,1017 / S0370164600044643.
Трахтман, Авраам Н. (2009), «Проблема раскраски дорог», Израильский математический журнал , 172 (1): 51–60, arXiv : 0709.0099 , doi : 10.1007 / s11856-009-0062-5 , S2CID 515742.
Визинг В.Г. (1964) "Об оценке хроматического класса p -графа", Дискрет. Анализ. , 3 : 25–30, MR 0180505.
Визинг В.Г. (1965) "Критические графы с заданным хроматическим классом", Методы Дискрет. Анализ. , 5 : 9–17. (По-русски.)
Уильямсон, Д.П . ; Холл, Луизиана; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Севастьянов С.В.; Shmoys, DB (1997), "графика Short магазина", исследование операций , 45 (2): 288-294, DOI : 10,1287 / opre.45.2.288 , JSTOR 171745 , MR 1644998.
Чжоу, Сяо; Накано, Син-ичи; Nishizeki, Такао (1996), "Край-раскраски частичных $K$ -дерев", журнал алгоритмы , 21 (3): 598-617, DOI : 10,1006 / jagm.1996.0061 , МР 1417666.

Languages

In other projects