Окраска кромок

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

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

Примеры

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

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

Полный граф 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, для раскраски ребер $O n$ требуется $n + 1$ цвет, но когда n равно 5, 6 или 7, требуется только $n цветов.$ ^[3]

Определения

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

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

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

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

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

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

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

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

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

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

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

Каждый двудольный граф имеет класс 1, ^[5] и почти все случайные графы имеют класс 1. ^[6] Однако задача определения, имеет ли произвольный граф класс 1, является NP-полной. ^[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)$ ребер, и каждые два ребра смежны, поэтому все ребра должны быть раскрашены в разные цвета). В результате, который вдохновил Визинга ^[10] , Шеннон (1949) показал, что это наихудший случай: $χ'(G) \leq (3/2)Δ(G)$ для любого мультиграфа $G$ . Кроме того, для любого мультиграфа G $χ$ $'(G) \leq Δ(G) + μ(G)$ , неравенство, которое сводится к теореме Визинга в случае простых графов (для которых $μ(G) = 1$ ).

Алгоритмы

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

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

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

Для планарных графов с максимальной степенью $Δ \geq 7$ оптимальное количество цветов снова равно $Δ$ . При более сильном предположении, что $Δ \geq 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). Количество цветов, используемых этим алгоритмом, не превышает , что близко, но не совсем совпадает с границей Шеннона . Его также можно превратить в параллельный алгоритм простым способом. В той же статье Карлофф и Шмойс также представляют алгоритм линейного времени для раскраски мультиграфов максимальной степени три четырьмя цветами (соответствующий границам Шеннона и Визинга), который работает по схожим принципам: их алгоритм добавляет новую вершину, чтобы сделать граф эйлеровым, находит эйлеров цикл, а затем выбирает чередующиеся наборы ребер в цикле, чтобы разбить граф на два подграфа максимальной степени два. Пути и четные циклы каждого подграфа могут быть раскрашены двумя цветами на подграф. После этого шага каждый оставшийся нечетный цикл содержит по крайней мере одно ребро, которое может быть раскрашено одним из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечетного цикла оставляет путь, который можно раскрасить, используя два цвета для его подграфа. $3\left\lceil {\frac {\Delta}{2}}\right\rceil$ $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$

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

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

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

Легко проверить, может ли граф быть раскрашен ребрами в один или два цвета, поэтому первый нетривиальный случай раскраски ребер — это проверка того, имеет ли граф 3-раскраску ребер. Как показал Ковалик (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 m)$ и только полиномиальное пространство (Бьёрклунд, Хусфельдт и Койвисто 2009).

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

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

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

Граф однозначно раскрашиваем в $k$ ребер, если существует только один способ разбиения ребер на $k$ цветовых классов, игнорируя $k!$ возможных перестановок цветов. Для $k \neq 3$ единственными однозначно раскрашиваемыми в $k$ ребер графами являются пути, циклы и звезды , но для $k = 3$ другие графы также могут быть однозначно раскрашиваемыми $в k$ ребер. Каждый однозначно раскрашиваемый в 3 ребра граф имеет ровно три гамильтоновых цикла (образованных путем удаления одного из трех цветовых классов), но существуют 3-регулярные графы, которые имеют три гамильтоновых цикла и не являются однозначно раскрашиваемыми в 3 цвета, такие как обобщенные графы Петерсена $G (6 n + 3, 2)$ для $n \geq 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-рёберно-раскрашенный 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$ $)$ совпадает с границей, заданной теоремой Визинга. ^[18] $\mathop {\mathrm {la} } (G)\leq \left\lceil {\frac {\Delta +1}{2}}\right\rceil$

Другие типы

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

Примечания

^ Сойфер (2008), задача 16.4, с. 133.
^ Сойфер (2008), задача 16.5, стр. 133. Тот факт, что требуется либо $n$ , либо $(n - 1)$ цветов, является примером теоремы Визинга .
^ Биггс (1972); Мередит и Ллойд (1973); Биггс (1979).
^ ab Soifer (2008), стр. 134.
^ Кёниг (1916)
^ Эрдёш и Уилсон (1977).
^ Холиер (1981).
^ Сандерс и Чжао (2001).
^ Тейт (1880); Аппель и Хакен (1976).
^ Сойфер (2008), стр. 136.
^ Бар-Ной, Мотвани и Наор (1992).
^ Бахмани, Мехта и Мотвани (2010).
^ Голдберг (1973); Андерсен (1977); Сеймур (1979).
^ Чэнь, Юй и Занг (2011).
^ Эппштейн (2013).
^ Швенк (1989).
^ Босак (1972).
^ Акияма, Эксу и Харари (1980); Хабиб и Перош (1982); Горак и Нипель (1982).
^ Нэш-Уильямс (1964).
^ Габов и Вестерманн (1992).
^ Босак и Нешетржил (1976).
^ Фуке и Жоливе (1983); Махдиан (2002); Фриз, Кривелевич и Судаков (2005); Крэнстон (2006).
^ Барретт и др. (2006).
^ Алон, Судаков и Закс (2001); Мутху, Нараянан и Субраманиан (2007).
^ Фиамчик (1978); Алон, Судаков и Закс (2001)
^ Джотис и др. (2015).
^ Алон, Судаков и Закс (2001).
^ Кай и др. (2014).
^ Эппштейн (2010).
^ Берк, Де Верра и Кингстон (2004).
^ Скиена (2008).
^ Уильямсон и др. (1997).
^ Эрлебах и Янсен (2001).
^ Чудновский, Эдвардс и Сеймур (2015).

Ссылки

Акияма, Джин; Эксо, Джеффри; Харари, Фрэнк (1980), «Покрытие и упаковка в графах. III. Циклические и ациклические инварианты», Mathematica Slovaca , 30 (4): 405–417, MR 0595302.
Алон, Нога (2003), «Простой алгоритм раскраски рёбер двудольных мультиграфов», Information Processing Letters , 85 (6): 301–302, doi :10.1016/S0020-0190(02)00446-5, MR 1956451, S2CID 34965604.
Алон, Нога ; Судаков, Бенни; Закс, Айал (2001), «Ациклические раскраски ребер графов», Журнал теории графов , 37 (3): 157–167, doi :10.1002/jgt.1010, MR 1837021.
Андерсен, Ларс Дёвлинг (1977), «О раскраске рёбер графов», Mathematica Scandinavica , 40 (2): 161–175, doi : 10.7146/math.scand.a-11685 , MR 0465922. Как цитируют Чэнь, Юй и Занг (2011).
Аппель, К.; Хакен , В. (1976), «Каждая плоская карта может быть раскрашена четырьмя цветами», Бюллетень Американского математического общества , 82 (5): 711–712, doi : 10.1090/S0002-9904-1976-14122-5 , MR 0424602.
Бахмани, Бахман; Мехта, Араньяк; Мотвани, Раджив (2010), «1,43-конкурентный онлайн-алгоритм раскраски ребер графа в модели случайного порядка прибытия», Труды двадцать первого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA '10), Общество промышленной и прикладной математики, стр. 31–39, ISBN 9780898716986.
Бар-Ной, Амоц; Мотвани, Раджив ; Наор, Джозеф (1992), «Жадный алгоритм оптимален для раскраски рёбер в режиме реального времени», Information Processing Letters , 44 (5): 251–253, doi :10.1016/0020-0190(92)90209-E.
Barrett, CL; Istrate, G.; Kumar, VSA; Marathe, MV; Thite, S.; Thulasidasan, S. (2006), "Сильная раскраска границ для назначения каналов в беспроводных радиосетях", Proc. Четвертая ежегодная международная конференция IEEE по всепроникающим вычислениям и семинарам по коммуникациям (PerCom Workshops 2006) , стр. 106, doi :10.1109/PERCOMW.2006.129, ISBN 0-7695-2520-2, S2CID 5797236.
Биггс, Норман (1972), Гай, Ричард К. (ред.), «Проблема раскрашивания рёбер», Research Problems, 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 Journal on Computing , 39 (2): 546–563, doi : 10.1137/070683933, MR 2529771.
Босак, Юрай (1972), «Хроматический индекс конечных и бесконечных графов», Czechoslovak Mathematical Journal , 22 (97): 272–290, doi : 10.21136/CMJ.1972.101098 , MR 0309777.
Босак, Юрай; Нешетржил, Ярослав (1976), «Полные и псевдополные раскраски графа», Matematicky Časopis Slovenskej Akadémie Vied , 26 (3): 171–184, MR 0439672.
Cai, XS; Perarnau, G.; Reed, BA ; Watts, AB (2014), "Ациклическая раскраска ребер графов с большим обхватом", Random Structures & Algorithms , 50 (4): 511–533, arXiv : 1411.3047 , doi : 10.1002/rsa.20695, S2CID 7727097.
Берк, Э.; Де Верра, Д.; Кингстон, Дж. (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-y, MR 2770056, S2CID 169162.
Чудновски, Мария ; Эдвардс, Кэтрин; Сеймур, Пол (ноябрь 2015 г.), «Раскраска рёбер восьмирегулярных планарных графов», Журнал комбинаторной теории , Серия B, 115 : 303–338, arXiv : 1209.1176 , doi : 10.1016/j.jctb.2015.05.002.
Коул, Ричард ; Хопкрофт, Джон (1982), «О раскраске ребер двудольных графов», SIAM Journal on Computing , 11 (3): 540–546, doi : 10.1137/0211043, hdl : 1813/6283 , MR 0664720.
Коул, Ричард; Ковалик, Лукаш (2008), «Новые алгоритмы линейного времени для раскраски рёбер планарных графов», Algorithmica , 50 (3): 351–368, doi :10.1007/s00453-007-9044-3, MR 2366985, S2CID 7692895.
Коул, Ричард; Ост, Кирстин; Ширра, Стефан (2001), «Раскраска рёбер двудольных мультиграфов за время $O(E log D)$ », Combinatorica , 21 (1): 5–12, doi :10.1007/s004930170002, MR 1805711, S2CID 522145.
Крэнстон, Дэниел В. (2006), «Сильная раскраска рёбер графов с максимальной степенью 4 с использованием 22 цветов», Дискретная математика , 306 (21): 2772–2778, arXiv : math/0601623 , Bibcode : 2006math......1623C, doi : 10.1016/j.disc.2006.03.053, MR 2264374, S2CID 1097275.
Эппштейн, Дэвид (2013), «Сложность рисования бессгибного трехмерного ортогонального графа», Журнал графовых алгоритмов и приложений , 17 (1): 35–55, arXiv : 0709.4087 , doi : 10.7155/jgaa.00283, S2CID 2716392.
Эппштейн, Дэвид (2010), «Регулярные маркировки и геометрические структуры», Труды 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.
Фербер, Асаф; Джейн, Вишеш (сентябрь 2020 г.), «1-факторизации псевдослучайных графов», Случайные структуры и алгоритмы , 57 (2): 259–278, arXiv : 1803.10361 , doi : 10.1002/rsa.20927, S2CID 4680445.
Fiamčik, J. (1978), "Ациклический хроматический класс графа", Math. Slovaca , 28 : 139–145.
Фиорини, С.; Уилсон, Робин Джеймс (1977), Раскраска рёбер графов , Research Notes in Mathematics, т. 16, Лондон: 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.
Фуке, Ж.-Л.; Жоливе, Ж.-Л. (1983), «Сильные раскраски рёбер графов и приложения к многоугольникам с числом $k$ », Ars Combinatoria , 16 (A): 141–150, MR 0737086.
Фриз, Алан М.; Кривелевич, Майкл; Судаков, Бенни (2005), «Сильный хроматический индекс случайных графов» (PDF) , SIAM Journal on Discrete Mathematics , 19 (3): 719–727 (электронный), doi :10.1137/S0895480104445757, MR 2191290.
Габов, Гарольд Н. (1976), «Использование разбиений Эйлера для раскраски двудольных мультиграфов», Международный журнал компьютерных и информационных наук , 5 (4): 345–355, doi :10.1007/BF00998632, MR 0422081, S2CID 36331285.
Габов, Гарольд Н.; Нишизеки , Такао ; Карив, Одед; Левен, Дэниел; Терада, Осаму (1985), Алгоритмы для раскраски ребер графов , Технический отчет TRECIS-8501, Университет Тохоку.
Габов, Гарольд Н.; Вестерманн, Герберт Х. (1992), «Леса, фреймы и игры: алгоритмы для сумм матроидов и приложений», Algorithmica , 7 (5–6): 465–497, doi :10.1007/BF01758774, MR 1154585, S2CID 40358357.
Галвин, Ф. (1995), «Списочный хроматический индекс двудольного мультиграфа», Журнал комбинаторной теории , Серия B, 63 (1): 153–158, doi : 10.1006/jctb.1995.1011.
Гандам, С.; Даванде, М.; Пракаш, Р. (2005), «Планирование связей в сенсорных сетях: пересмотр распределенной раскраски ребер», Proc. 24th INFOCOM , т. 4, стр. 2492–2501, doi :10.1109/INFCOM.2005.1498534, ISBN 0-7803-8968-9, S2CID 8085139.
Джотис, И.; Кирусис, Л.; Псаромилигкос, КИ; Тиликос, ДМ (2015), «Об алгоритмической локальной лемме Ловаса и ациклической раскраске ребер», Труды Двенадцатого семинара по аналитической алгоритмике и комбинаторике (ANALCO) , стр. 16, doi : 10.1137/1.9781611973761.2 , ISBN 978-1-61197-376-1.
Голдберг, МК (1973), «Мультиграфы с хроматическим индексом, близким к максимальному», Дискретный анализ (23): 3–7, 72, MR 0354429. Как цитируют Чэнь, Юй и Занг (2011).
Хабиб, М.; Перош, Б. (1982), «Некоторые проблемы линейной древесности», Дискретная математика , 41 (2): 219–220, doi : 10.1016/0012-365X(82)90209-6 , MR 0676882.
Холиер, Ян (1981), «NP-полнота раскраски рёбер», SIAM Journal on Computing , 10 (4): 718–720, doi :10.1137/0210055, S2CID 13131049.
Горак, Питер; Нипель, Людовит (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.
Кениг, Д. (1916), «Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre», Mathematische Annalen , 77 (4): 453–465, doi : 10.1007/BF01456961, hdl : 10338.dmlcz/127635 , S2CID 121097364, заархивировано из оригинала 19 января 2015 г. , получено 30 сентября 2013 г..
Ковалик, Лукаш (2009), «Улучшенная раскраска рёбер тремя цветами», Теоретическая информатика , 410 (38–40): 3733–3742, doi : 10.1016/j.tcs.2009.05.005 , MR 2553326.
Махдиан, Мохаммад (2002), «О вычислительной сложности сильной раскраски рёбер», Discrete Applied Mathematics , 118 (3): 239–248, doi : 10.1016/S0166-218X(01)00237-2 , MR 1892971.
Мередит, Гай Х. Дж.; Ллойд, Э. Кит (1973), «Футболисты Кроама», Журнал комбинаторной теории , Серия B, 15 (2): 161–166, doi : 10.1016/0095-8956(73)90016-6.
Мисра, Дж.; Грайс, Дэвид (1992), «Конструктивное доказательство теоремы Визинга», Information Processing Letters , 41 (3): 131–133, doi :10.1016/0020-0190(92)90041-S.
Muthu, Rahul; Narayanan, N.; Subramanian, CR (2007), "Улучшенные границы ациклической раскраски ребер", Discrete Mathematics , 307 (23): 3063–3069, doi : 10.1016/j.disc.2007.03.006 , MR 2371078.
Nash-Williams, C. St. JA (1964), «Разложение конечных графов на леса», Журнал Лондонского математического общества , Вторая серия, 39 : 12, doi : 10.1112/jlms/s1-39.1.12, MR 0161333
Немхаузер, Джордж Л.; Пак, Сангсу (1991), «Многогранный подход к раскраске рёбер», Operations Research Letters , 10 (6): 315–322, doi :10.1016/0167-6377(91)90003-8, MR 1128970.
Richter, David A. (2011), «Как нарисовать граф, раскрашиваемый по Тейту», в Брандес, Ульрик ; Корнельсен, Сабина (ред.), Proc. 18th International Symposium on Graph Drawing (GD 2010) , Lecture Notes in Computer Science, т. 6502, Springer-Verlag, стр. 353–364, doi : 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.
Сеймур, П.Д. (1979), «О многоцветных кубических графах и гипотезах Фулкерсона и Тутта», Труды Лондонского математического общества , Третья серия, 38 (3): 423–460, doi :10.1112/plms/s3-38.3.423, MR 0532981.
Швенк, Аллен Дж. (1989), «Перечисление гамильтоновых циклов в некоторых обобщенных графах Петерсена», Журнал комбинаторной теории , Серия B, 47 (1): 53–59, doi : 10.1016/0095-8956(89)90064-6 , MR 1007713.
Шеннон, Клод Э. (1949), «Теорема о раскраске линий сети», J. Math. Physics , 28 (1–4): 148–151, doi : 10.1002/sapm1949281148, hdl : 10338.dmlcz/101098 , MR 0030203.
Скиена, Стивен С. (2008), «16.8 Раскраска рёбер», Руководство по разработке алгоритмов (2-е изд.), Springer-Verlag, стр. 548–550, doi :10.1007/978-1-84800-070-4_16, ISBN 978-1-84800-069-8. См. также веб-сайт этого раздела книги в репозитории алгоритмов Стоуни-Брук.
Сойфер, Александр (2008), Математическая раскраска , Springer-Verlag, ISBN 978-0-387-74640-1.
Тейт, ПГ (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. (На русском языке.)
Уильямсон, ДП ; Холл, Луизиана; Хугевен, Дж.А.; Хюркенс, CAJ; Ленстра, JK ; Севастьянов С.В.; Шмойс, Д.Б. (1997), «Краткие графики цехов», Operations Research , 45 (2): 288–294, doi : 10.1287/opre.45.2.288, JSTOR 171745, MR 1644998.
Чжоу, Сяо; Накано, Син-ити; Нишизеки, Такао (1996), «Раскрашивание рёбер частичных $k$ -деревьев», Журнал алгоритмов , 21 (3): 598–617, doi :10.1006/jagm.1996.0061, MR 1417666.