Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Трехреберная раскраска графа Дезарга .

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

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

Примеры [ править ]

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

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

Полный граф К п с п вершинами ребра раскрашиваемого с п - 1 цветы , когда п является четным числом; это частный случай теоремы Бараньяи . Сойфер (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 цвет, но когда это 5, 6 или 7, необходимо только n цветов. [3]

Определения [ править ]

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

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

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

Отношение к сопоставлению [ править ]

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

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

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

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

Отношение к степени [ править ]

Теорема Визинга [ править ]

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

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

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

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

Обычные графики [ править ]

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

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

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

Мультиграфы [ править ]

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

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

Алгоритмы [ править ]

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

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

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

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

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

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

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

Для мультиграфов Карлофф и Шмойс (1987) представляют следующий алгоритм, который они приписывают Эли Упфалу . Сделайте входной мультиграф G эйлеровым , добавив новую вершину, соединенную ребром с каждой вершиной нечетной степени, найдите эйлеров тур и выберите его ориентацию. Сформируйте двудольный граф H, в котором есть две копии каждой вершины G , по одной на каждой стороне двудольного раздела, с ребром от вершины u на левой стороне двудольного до вершины v на правой стороне двудольного. если ориентированный тур имеет ребро от u до v в G. Нанесите двудольный граф реберной раскраски алгоритм к H . Каждый цветовой класс в H соответствует набору ребер в G, которые образуют подграф с максимальной степенью два; то есть объединение непересекающихся путей и циклов, поэтому для каждого класса цвета в H можно сформировать три цветовые классы в G . Время для алгоритма ограничено временем окраски ребер двудольного графа, O ( m log Δ), с использованием алгоритма Коула, Оста и Ширры (2001) . Количество цветов, используемых в этом алгоритме, максимально близко, но не совсем то же, что и оценка Шеннона . Это также может быть преобразовано в параллельный алгоритмпростым способом. В той же статье Карлофф и Шмойс также представляют алгоритм линейного времени для раскраски мультиграфов максимальной степени три в четыре цвета (совпадающих с границами Шеннона и Визинга), который работает на аналогичных принципах: их алгоритм добавляет новую вершину, чтобы сделать граф эйлеровым, находит эйлеров тур, а затем выбирает чередующиеся наборы ребер в обходе, чтобы разбить граф на два подграфа максимальной степени два. Пути и даже циклы каждого подграфа могут быть раскрашены двумя цветами для каждого подграфа. После этого шага каждый оставшийся нечетный цикл содержит по крайней мере одно ребро, которое может быть окрашено в один из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечетного цикла оставляет путь, который можно раскрасить двумя цветами для его подграфа.

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

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

Точные алгоритмы [ править ]

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

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

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

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

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

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

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

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

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

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

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

Хроматический индекс не только связан с максимальной степенью и максимальным числом совпадений графа, но и с линейной древовидностью la ( G ) графа G , минимальным количеством линейных лесов (непересекающихся объединений путей), в которые ребра графа могут быть разбиты. Паросочетание - это особый вид линейного леса, и в обратном направлении любой линейный лес может быть 2-крашен по ребрам, поэтому для любого G следует, что la ( G ) ≤ χ ′ ( G ) ≤ 2 la ( G ) . Гипотеза Акиямы (названная в честь Джин Акияма ) гласит, что , из чего будет более четко следовать, что2 la ( G ) - 2 ≤ χ ′ ( G ) ≤ 2 la ( G ) . Для графов максимальной степени три la ( G ) всегда ровно два, поэтому в этом случае оценка χ ′ ( G ) ≤ 2 la ( G ) совпадает с оценкой, данной теоремой Визинга. [18]

Другие типы [ править ]

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

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

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

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

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

Ациклическая раскраска ребер - это вариант раскраски ребер ациклической раскраски , раскраски ребер, для которой каждые два цветовых класса образуют ациклический подграф (то есть лес). [24] Ациклический хроматический индекс графа , обозначаемый , - это наименьшее количество цветов, необходимых для правильной ациклической окраски ребер . Было высказано предположение, что , где - максимальная степень . [25] В настоящее время наиболее известной оценкой является . [26] Проблема становится легче, когда у тебя большой обхват . Точнее, существует такая константа , что если обхват не меньше , то .[27] Аналогичный результат состоит в том, что для всехсуществуеттакое, что еслиимеет хотя бы обхват, то. [28]

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

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

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

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

Теорема Рамсея касается проблемы k -раскрашивания ребер большого полного графа K n , чтобы избежать создания монохроматических полных подграфов K s некоторого заданного размера  s . Согласно теореме существует такое число R k ( s ) , что при n ≥ 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.
  • Переполнена подграф гипотеза о AJW Hilton, указав , что графики со степенью , по крайней мере п / 3 являются либо из класса 1 или содержат подграф с той же степенью А в качестве исходного графа, и с нечетным числом к вершинам, например , что число ребер в подграфе больше ∆ ( k - 1) / 2 , и аналогичная гипотеза Герберта Грётша и Пола Сеймура о плоских графах вместо графов высокой степени.
  • Гипотеза Аманды Четвинд и Энтони Хилтона (возможно, восходящая к ранее работам Габриэля Эндрю Дирака ) о том, что регулярные графы с четным числом вершин n и степенью не менее n / 2 относятся к классу 1.
  • Гипотеза Клода Берже и Д. Р. Фулкерсона о том, что 6-регулярные мультиграфы, образованные удвоением каждого ребра 3-регулярного простого графа без мостов, могут быть окрашены ребрами в шесть цветов.
  • Гипотеза Фиорини и Вильсона о том, что любой плоский граф без треугольников , кроме когтя K 1,3 , не является однозначно 3-краскируемым .
  • Гипотеза 2012 года о том, что если G является d -регулярным плоским мультиграфом, то G является d- реберно-раскрашиваемым тогда и только тогда, когда G имеет нечетную d- реберную связность. Эта гипотеза является обобщением теоремы о четырех цветах , возникающей при d = 3. Мария Чудновская , Кэтрин Эдвардс и Пол Сеймур доказали, что 8-регулярный плоский мультиграф имеет хроматическое число ребер, равное 8. [34]

Примечания [ править ]

  1. ^ Сойфер (2008) , проблема 16.4, стр. 133.
  2. ^ Сойфер (2008) , проблема 16.5, стр. 133. Тот факт, чтотребуетсялибо n, либо ( n - 1) цветов, является примером теоремы Визинга .
  3. ^ Биггс (1972) ; Мередит и Ллойд (1973) ; Биггс (1979) .
  4. ^ а б Сойфер (2008) , стр. 134.
  5. ^ Кениг (1916)
  6. Перейти ↑ Erdős & Wilson (1977) .
  7. ^ Холиер (1981) .
  8. ^ Сандерс и Чжао (2001) .
  9. ^ Тейт (1880) ; Аппель и Хакен (1976) .
  10. ^ Сойфер (2008) , стр. 136.
  11. ^ Бар-Noy, Motwani & Naor (1992) .
  12. ^ Бахмани, Мехта и Motwani (2010) .
  13. ^ Голдберг (1973) ; Андерсен (1977) ; Сеймур (1979) .
  14. Перейти ↑ Chen, Yu & Zang (2011) .
  15. ^ Эпштайна (2013) .
  16. ^ Швенк (1989) .
  17. ^ Босак (1972) .
  18. ↑ Акияма, Эксу и Харари (1980) ; Хабиб и Перош (1982) ; Хорак и Непель (1982) .
  19. ^ Нэш-Уильямс (1964) .
  20. ^ Gabow & Вестерманн (1992) .
  21. ^ Bosak & Nešetřil (1976) .
  22. ↑ Fouquet & Jolivet (1983) ; Махдиан (2002) ; Фриз, Кривелевич и Судаков (2005) ; Крэнстон (2006) .
  23. ^ Barrett et al. (2006) .
  24. ^ Алон, Судаков и Закс (2001) ; Мутху, Нараянан и Субраманиан (2007) .
  25. ^ Fiamčik (1978) ; Алон, Судаков и Закс (2001)
  26. ^ Giotis et al. (2015) .
  27. ↑ Алон, Судаков и Закс (2001) .
  28. ^ Cai et al. (2014) .
  29. ^ Эпштайна (2010) .
  30. Перейти ↑ Burke, De Werra & Kingston (2004) .
  31. ^ Skiena (2008) .
  32. ^ Уильямсон и др. (1997) .
  33. ^ Эрлебах и Янсен (2001) .
  34. ^ Чудновский, Эдвардс и Сеймур (2012) .

Ссылки [ править ]

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