Краевая окраска

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

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

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

Примеры

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

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

Полный граф K _n с n вершинами можно раскрасить по ребрам в n − 1 цвет, если n — четное число; это частный случай теоремы Бараньи . Сойфер (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 ₆ . Когда n раскраски ребер On _{равно 3, 4 или 8, для} требуется n + 1 цветов, но когда оно равно 5, 6 или 7, только n цветов. требуется

Определения

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

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

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

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

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

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

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

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

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

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

Основная статья: теорема Визинга

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

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

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

Обычные графики

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

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

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

Мультиграфы

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

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

Алгоритмы

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

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

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

Для плоских графов с максимальной степенью Δ ≥ 7 оптимальное количество цветов снова равно именно Δ . При более сильном предположении, что Δ ≥ 9 , можно найти оптимальную раскраску ребер за линейное время ( Коул и Ковалик 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 цветов, что может быть почти в два раза больше цветов, чем необходимо. Однако у него есть то преимущество, что его можно использовать в настройках онлайн-алгоритма, в которых входной граф заранее не известен; в таких условиях его коэффициент конкурентоспособности равен двум, и это оптимально: ни один другой онлайн-алгоритм не сможет достичь лучшей производительности. Однако если ребра поступают в случайном порядке и входной граф имеет степень, по меньшей мере, логарифмическую, то можно достичь меньших коэффициентов конкуренции.

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

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

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

Применяя точные алгоритмы раскраски вершин к линейному графу входного графа, можно оптимально раскрасить ребра любого графа с m ребрами, независимо от количества необходимых цветов, за время 2. ^м м ^О(1) и экспоненциальном пространстве или во времени O(2,2461 ^м ) и только полиномиальное пространство ( Björklund, Husfeldt & Koivisto 2009 ).

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

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

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

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

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

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

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

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

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

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

Другие типы

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

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

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

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

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

Дженсен и Тофт (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.

Ссылки

• Акияма, Джин; Эксу, Джеффри; Харари, Франк (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), «Ациклические раскраски ребер графов», Journal of Graph Theory , 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 . Цитируется Chen, Yu & Zang (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 .
• Барретт, CL; Истрате, Г.; Кумар, ВСА; Марат, МВ; Тите, С.; Туласидасан, С. (2006), «Сильная окраска границ для назначения каналов в беспроводных радиосетях», Proc. Семинары Четвертой ежегодной международной конференции IEEE по всеобъемлющим вычислениям и коммуникациям (PerCom Workshops 2006) , стр. 106, номер домена : 10.1109/PERCOMW.2006.129 , ISBN  0-7695-2520-2 , S2CID   5797236 .
• Биггс, Норман (1972), Гай, Ричард К. (редактор), «Проблема раскраски ребер», Research Issues, American Mathematical Monthly , 79 (9): 1018–1020, doi : 10.2307/2318076 , JSTOR   2318076 .
• Биггс, Норман (1979), «Некоторая странная теория графов», Вторая международная конференция по комбинаторной математике, Анналы Нью-Йоркской академии наук , 319 (1): 71–81, Бибкод : 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), «Хроматический индекс конечных и бесконечных графов», Чехословацкий математический журнал , 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 .
• Цай, XS; Перарнау, Г.; Рид, Бакалавр ; Уоттс, AB (2014), «Ациклические раскраски ребер графов с большим обхватом», Случайные структуры и алгоритмы , 50 (4): 511–533, arXiv : 1411.3047 , doi : 10.1002/rsa.20695 , S2CID   7727097 .
• Берк, Э.; Де Верра, Д.; Кингстон, Дж. (2004), «5.6.5 Расписание занятий спортом» , в JL, Гросс; Йеллен Дж. (ред.), Справочник по теории графов , CRC Press, стр. 462, ISBN  978-1-58488-090-5 .
• Чен, Гуантао; Ю, Синсин; Занг, Вэнань (2011), «Аппроксимация хроматического индекса мультиграфов», Journal of Combinatorial Optimization , 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 цветов», Discrete Mathematics , 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), «Регулярные разметки и геометрические структуры», 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), «Сложность раскраски путей и планирования вызовов», Theoretical Computer Science , 255 (1–2): 33–50, doi : 10.1016/S0304-3975(99)00152-8 , MR   1819065 .
• Фербер, Асаф; Джайн, Вишеш (сентябрь 2020 г.), «1-факторизация псевдослучайных графов», Random Structures & Algorithms , 57 (2): 259–278, arXiv : 1803.10361 , doi : 10.1002/rsa.20927 , S2CID   4680445 .
• Фиамчик, Дж. (1978), «Ациклический хроматический класс графа», Math. Словака , 28 : 139–145 .
• Фиорини, С.; Уилсон, Робин Джеймс (1977), Раскраска ребер графов , Исследовательские заметки по математике, том. 16, Лондон: Питман, ISBN  0-273-01129-4 , МР   0543798 .
• Фолкман, Джон ; Фулкерсон, Д.Р. (1969), «Раскраски ребер в двудольных графах», Комбинаторная математика и ее приложения (Proc. Conf., Univ. Северной Каролины, Чапел-Хилл, Северная Каролина, 1967) , Чапел-Хилл, Северная Каролина: 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), Алгоритмы раскраски ребер графов , Tech. Отчет 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. 24-й ИНФОКОМ , вып. 4, стр. 2492–2501, номер документа : 10.1109/INFCOM.2005.1498534 , ISBN.  0-7803-8968-9 , S2CID   8085139 .
• Гиотис, И.; Кирусис, Л.; Псаромилигкос, К.И.; Тиликос, Д.М. (2015), «Об алгоритмической локальной лемме Ловаса и ациклической раскраске ребер», Материалы двенадцатого семинара по аналитической алгоритмике и комбинаторике (ANALCO) , с. 16, номер домена : 10.1137/1.9781611973761.2 , ISBN  978-1-61197-376-1 .
• Гольдберг, М.К. (1973), «Мультиграфы с хроматическим индексом, близким к максимальному», Дискрет. Анализ. (23): 3–7, 72, МР   0354429 . Цитируется Chen, Yu & Zang (2011) .
• Хабиб, М.; Перош, Б. (1982), «Некоторые проблемы, связанные с линейной древесностью», Discrete Mathematics , 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), «О графах и их применении к теории определителей и теории множеств» , Mathematical Annals , 77 (4): 453–465, doi : 10.1007/BF01456961 , hdl : 10338.dmlcz/127635 , S2CID   121097364 , заархивировано из оригинала 19 января 2015 г. , получено г. 30 сентября 2013
• Ковалик, Лукаш (2009), «Улучшенная раскраска краев тремя цветами», Theoretical Computer Science , 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 .
• Мутху, Рахул; Нарайанан, Н.; Субраманиан, CR (2007), «Улучшенные границы ациклической раскраски ребер», Discrete Mathematics , 307 (23): 3063–3069, doi : 10.1016/j.disc.2007.03.006 , MR   2371078 .
• Нэш-Уильямс, К. Ст. Дж. А. (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 .
• Рихтер, Дэвид А. (2011), «Как нарисовать граф, раскрашиваемый по Тейту», в Брандесе, Ульрике ; Корнельсен, Сабина (ред.), Proc. 18-й Международный симпозиум по рисованию графов (GD 2010) , Конспекты лекций по информатике, том. 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 .
• Сеймур, П.Д. (1979), «О раскраске кубических графов и гипотезах Фулкерсона и Тутте», Труды Лондонского математического общества , третья серия, 38 (3): 423–460, doi : 10.1112/plms/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 , 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. Р. Сок. Эдинбург , 10 :729, номер номера : 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, МР   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 », Journal of Algorithms , 21 (3): 598–617, doi : 10.1006/jagm.1996.0061 , MR   1417666 .