Рёберная раскраска

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Рёберная 3-цветная раскраска графа Дезарга.

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

По теореме Визинга, число цветов, необходимых для рёберной раскраски простого графа либо равно максимальной степени \Delta, либо \Delta+1. Для некоторых графов, таких как двудольные графы и планарные графы высокой степени, число цветов всегда равно \Delta, а для мультиграфов число цветов может быть вплоть до 3{\Delta}/2. Существуют алгоритмы полиномиального времени, создающие оптимальную раскраску двудольных графов и раскраску простого не двудольного графа с числом цветов {\Delta}+1. Однако, в общем случае, задача поиска оптимальной рёберной раскраски NP-полна и самый быстрый из известных алгоритмов для неё работает за экспоненциальное время. Изучались много вариантов задачи рёберной раскраски, в которых условия назначения цвета ребру должны удовлетворять другим условиям, а не сопряжённости. Задачи рёберной раскраски имеют приложения в задачах расписания и в назначении частоты в оптоволоконных сетях.

Примеры[править | править вики-текст]

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

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

Рёбра полного графа K_n с n вершинами могут быть раскрашены n - 1 цветами, если n чётно. Это специальный случай теоремы Бараньяи[en]. Сойфер [2] даёт следующее геометрическое построение раскраски в этом случае: разместим n точек в углах и в центре правильного (n - 1)-угольника. Для каждого класса цвета выберем одно ребро, соединяющее центр и одну из вершин многоугольника, и все перпендикулярные ему рёбра, соединяющие пары вершин многоугольника. Однако, если n нечётно, требуется n цветов — каждый цвет можно использовать только для раскраски (n - 1)/2 рёбер, 1/n-ю часть всех рёбер.[3]

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

Определения[править | править вики-текст]

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

Правильная раскраска k различными цветами называется (правильной) рёберной k-раскраской. Если для графа можно найти (правильную) рёберную k-раскраску, говорят, что он рёберно k-раскрашиваем. Наименьшее число цветов, необходимых для (правильной) рёберной раскраски графа G называется хроматическим индексом, или рёберных хроматическим числом \chi{\prime}(G). Хроматический индекс иногда записывается в виде \chi_1(G). В этой нотации индекс показывает, что рёбра являются одномерными объектами. Граф является рёберно k-цветным, если хроматический индекс в точности равен k. Хроматический индекс не следует путать с хроматическим числом \chi (G) или \chi _0(G), минимальным числом цветов, необходимых для правильной раскраски вершин графа  G.

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

Связь с паросочетаниями[править | править вики-текст]

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

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

Если размер максимального паросочетания в заданном графе мал, необходимо большое число паросочетаний для покрытия всех рёбер графа. Выражая более формально, это объяснение предполагает, что если граф имеет m рёбер и если максимум \beta рёбер могут принадлежать максимальному паросочетанию, то каждая рёберная раскраска графа должна содержать по меньшей мере m/\beta различных цветов.[6] Например, планарный граф с 16 вершинами, показанный на иллюстрации имеет m = 24 рёбер. В этом графе нет совершенного паросочетания — если центральна вершина принадлежит паросочетанию, оставшиеся вершины можно разбить на три связных группы с числом вершин 4, 5, 5. Получившиеся подграфы с нечётным числом вершин не имеют совершенного паросочетания. Тем не менее, граф имеет максимальное паросочетание с семью рёбрами, так что \beta = 7. Поэтому число цветов, необходимых для рёберной раскраски графа, равно как минимум 24/7, а поскольку число цветов должно быть целым, получаем как минимум четыре цвета.

Для регулярных графов степени k, не имеющих совершенного паросочетания, эта нижняя граница может быть использована, чтобы показать, что необходимо как минимум k + 1 цветов.[6] В частности, это верно для регулярных графов с нечётным числом вершин. Для таких графов, по лемме о рукопожатиях, k должно быть, в свою очередь, нечётным. Однако неравенство\chi {\prime} \ge m\beta не полностью объясняет хроматический индекс произвольного регулярного графа, поскольку есть регулярные графы, имеющие совершенное паросочетание, но не рёберно k-раскрашиваемы. Например, граф Петерсена регулярен с m = 15 и с \beta = 5 рёбрами в совершенном паросочетании, но он не имеет рёберной 3-раскраски.

Связь со степенью[править | править вики-текст]

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

Рёберное хроматическое число графа G тесно связано с максимальной степенью {\Delta}(G) (максимальное число рёбер, смежных любой отдельной вершине графа G). Ясно, что \chi {\prime}(G) \ge {\Delta}(G), так что если {\Delta} различных рёбер содержат вершину v, то все эти рёбра должны быть раскрашены в различные цвета, что возможно только если имеется как минимум \Delta цветов. Теорема Визинга (названа в честь Вадима Визинга[en], опубликовавшего её в 1964) утверждает, что эта граница почти точна — для любого графа, рёберное хроматическое число равно либо {\Delta}(G), либо \Delta(G) + 1. Если \chi {\prime}(G) = {\Delta}(G), говорят, что G имеет класс 1, в противном случае говорят о классе 2.

Любой двудольный граф имеет класс 1 [7] и почти все случайные графы имеют класс 1.[8] Однако, задача проверки, имеет ли произвольный граф класс 1, является NP-полной задачей.[9]

Визинг 1965 доказал, что планарные графы максимальной степени не менее восьми имеют класс 1 и высказал гипотезу, что то же самое верно для планарных графов степени семь или шесть. С другой стороны, существуют планарные графы с максимальной степенью от двух до пяти, имеющие класс два. С тех пор гипотеза доказана для семи. [10]. Планарные графы без мостов, Кубические графы имеют класс 1, и это равносильно формулировке задачи о четырёх красках.[11]

Регулярные графы[править | править вики-текст]

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

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

Согласно теореме Кёнига [7] любой двудольный регулярный граф имеет 1-факторизацию. Теорема была сформулирована ранее в терминах проективных конфигураций[en] и была доказана Эрнстом Стейницем.

Мультиграфы[править | править вики-текст]

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

Для мультиграфов, в которых несколько рёбер могут соединять те же самые две вершины, известны похожие на теорему Визинга, но более слабые результаты относительно рёберного хроматического числа \chi {\prime}(G), максимальной степени \Delta(G) и кратности \mu(G), максимального числа рёбер в связке параллельных рёбер (то есть имеющих одни и те же конечные вершины). В качестве простого примера, показывающего, что теорема Визинга не обобщается на мультиграфы, рассмотрим мультиграф Шеннона, мультиграф с тремя вершинами и тремя связками \mu(G) параллельных рёбер, соединяющих каждую пару вершин. В этом примере, \Delta(G) = 2\mu(G) (каждая вершина смежна только двум из трёх связок \mu(G) параллельных рёбер) но рёберное хроматическое число равно 3\mu(G) (в графе 3\mu(G) рёбер и любые два ребра смежны, так что все рёбра должны быть раскрашены в разные цвета). В работе, навеянной теоремой Визинга, Сойфер и Шеннон[12] [13] показали, что это худший случай — \chi {\prime}(G) \le (3/2)\Delta(G) для любого мультиграфа G. Вдобавок, для любого мультиграфа G \chi {\prime}(G) \le \Delta(G) + \mu(G). Это неравенство сводится к теореме Визинга для простых графов (для них \mu(G) = 1).

Алгоритмы[править | править вики-текст]

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

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

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

Для планарных графов с максимальной степенью {\Delta}\ge 7 оптимальное число цветов снова равно в точности \Delta. При более строгом предположении, что {\Delta}\ge 9, можно найти оптимальную рёберную раскраску за линейное время (Коул, Ковалик 2008).

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

Мисра и Гриз (Мисра, Гриз 1992) и Габров (Габров и др. 1985) описывают алгоритм полиномиального времени раскраски любого графа с \Delta + 1 цветами, что соответствует границе, задаваемой теоремой Визинга.

Для мультиграфов Карлоф и Шмойс (Карлоф, Шмойс 1987) представили следующий алгоритм, который они приписывают Эли Упфалу[en]. Сделаем исходный мультиграф G эйлеровым путём добавления вершины, соединённой рёбрами со всеми вершинами нечётной степени, находим эйлеров путь и выбираем ориентацию для этого пути. Создаём двудольный граф H, который содержит две копии каждой вершины графа G, по одной в каждой доле, и рёбрами из вершины u в левой доле в вершину v в правой доле, когда ориентированный путь имеет дугу из u в v в графе G. Применим алгоритм рёберной раскраски двудольного графа для графа H. Каждый цвет в H соответствует множеству рёбер в G, которое образует подграф с максимальной степенью два, то есть, несвязное объединение путей и циклов, так что для каждого цвета в H можно образовать три цвета в G. Время работы алгоритма ограничено временем раскраски двудольного графа O(m\,log \Delta) при использовании алгоритма Коула, Оста и Ширра (Коул, Ост, Ширра 2001). Число цветов, которое использует этот алгоритм, не превосходит 3 \left\lceil\frac{\Delta}2\right\rceil, что близко, но не совсем то же самое, что граница Шеннона \left\lfloor\frac{3\Delta}2\right\rfloor. То же самое можно сделать с помощью параллельного алгоритма напрямую. В той же статье Карлофф и Шмойс предлагают также алгоритм с линейным временем работы для раскраски мультиграфов максимум третьей степени четырьмя цветами (что удовлетворяет как границе Шеннона, так и границе Визинга). Этот алгоритм работает по похожим принципам — алгоритм также добавляет вершину, чтобы сделать граф эйлеровым, находит эйлеров путь, а затем выбирает чередующиеся множества рёбер в пути чтобы разбить граф на два подмножества максимальной степени два. Пути и чётные циклы каждого подмножества можно выкрасить двумя цветами (по два цвета на подграф). Следующим шагом раскрашиваются рёбра нечётных циклов, в которых по меньшей одно ребро может быть раскрашено одним из двух цветов, принадлежащих противоположному подграфу. Удаление этого ребра из нечётного цикла оставляет путь, который можно раскрасить двумя цветами.

Алгоритм жадной раскраски, выбирающий последовательно рёбра графа или мультиграфа и назначающий первый допустимый цвет, может иногда использовать 2{\Delta}- 1 цветов, что может почти вдвое превосходить необходимое число цветов. Однако он имеет то преимущество, что он может быть использован в онлайн алгоритмах[en], ничего не знающих заранее о структуре графа. При указанных условиях его конкурентный коэффициент[en] равен двум, и этот коэффициент оптимален — никакой другой алгоритм не может дать показатели лучше.[14] Однако, если рёбра поступают в случайном порядке и исходный граф имеет степень как минимум логарифмическую, можно получить меньший конкурентный коэффициент.[15].

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

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

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

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

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

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

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

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

Граф однозначно[en] рёберно k-раскрашиваем тогда и только тогда, когда существует только один способ разбить рёбра на k классов цветов, не считая k! возможных перестановок цветов. Для k \ne 3 однозначно рёберно k-раскрашиваемыми графами являются только пути, циклы и звёзды, но для k = 3 могут быть однозначно рёберно k-раскрашиваемыми и другие графы. Любой однозначно рёберно 3-раскрашиваемый граф имеет ровно три гамильтоновых цикла (образованных путём удаления одного их трёх цветов), однако существуют 3-регулярные графы, имеющие три гамильтоновых цикла, но не имеющие однозначной рёберной 3-раскраски, как, например, обобщённые графы Петерсена G(6n + 3, 2) для n \ge 2. Известен всего один непланарный однозначно рёберно 3-раскрашиваемый граф, это обобщённый Граф Петерсена G(9,2), и есть гипотеза, что других не существует.[19]

Полный двудольный граф K3,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 в цепи Кемпе[en], наибольшем пути из рёбер, чередующих два цвета. В частности, любой граф имеет справедливую[en] рёберную раскраску, рёберную раскраску с оптимальным числом цветов, в которой два класса цветов по размеру отличаются максимум на единицу.

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

Рихтер (Рихтер 2011) рассматривает задачу поиска рисунка данного кубического графа со свойствами, что все рёбра в рисунке имеют один из трёх различных углов наклона и никакие два ребра не лежат на одной прямой. Если такое представление графа на рисунке существует, ясно, что угол наклона рёбер можно рассматривать как цвет рёбер в трёхцветной раскраске графа. Например, рисунок графа ресурсов K_{3,3} в виде рёбер и длинных диагоналей правильного шестиугольника представляет рёберную 3-раскраску графа таким способом. Как показал Рихтер, 3-регулярный двудольный граф с заданной раскраской Тайта имеет графическое представление такого вида тогда и только тогда, когда он k-рёберно связен[en]. Для недвудольных графов условие чуть сложнее — заданная раскраска может быть представлена такого рода рисунком, если двойное двудольное покрытие[en] графа 3-рёберно связно и если удаление двух одинаково раскрашенных рёбер приводит к недвудольному подграфу. Все эти условия легко проверить за полиномиальное время, однако задача проверки, имеет ли рёберно 4-раскрашенный 4-регулярный граф рисунок с четырьмя углами наклона, соответствующих цветам, является полной для теории существования вещественных чисел[en], того же класса сложности, что и NP-полнота.

Имея связь с максимальной степенью и максимальным числом паросочетаний графа, хроматический индекс тесно связан также с древесностью[en] la(G) графа G, минимальному числу линейных лесов (несвязному объединению путей), на которые рёбра графа могут быть разбиты. Паросочетание — это специальный вид линейного леса, но с другой стороны, любой линейный лес может быть рёберно 2-раскрашен, так что для любого G la(G) \le \chi {\prime}(G) \le 2 la(G). Гипотеза Акияма утверждает, что \mathop{\mathrm{la}}(G) \leq \left\lceil\frac{{\Delta}+1}{2}\right\rceil, откуда следовало бы более сильное неравенство 2 la(G) - 2 \le \chi {\prime}(G) \le 2 la(G). Для графов максимальной степени три la(G) всегда в точности равно двум, так что ограничение \chi {\prime}(G) \le 2 la(G) соответствует границе, следующей из теоремы Визинга.[21]

Другие типы рёберной раскраски[править | править вики-текст]

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

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

Древесность[en] графа — это минимальное число цветов, требующихся для раскраски таки образом, что рёбра любого цвета не содержит циклов (а не как в стандартной задаче раскраски — рёбра одного цвета несмежны). Таким образом, это минимальное число элементов леса, в которые можно разложить рёбра графа.[22] В отличие от хроматического числа ширина леса может быть вычислена за полиномиальное время.[23]

Задача предписанной раскраски рёбер[en] — это задача, в которой для заданного графа, для каждой дуги которого задан список цветов, нужно найти подходящую раскраску рёбер, в которой каждый цвет берётся из заданного списка. Предписанный хроматический индекс графа G — это наименьшее число k, при котором независимо от выбора списков цветов для рёбер, если для каждого ребра задано не менее k цветов, раскраска гарантированно существует. Предписанный хроматический индекс всегда не меньше хроматического числа. Гипотезу Диница[en] о заполнении частичных латинских квадратов можно перефразировать как утверждение, что предписанное рёберное хроматическое число полного двудольного графа K_{n,n} равнj его рёберному хроматическому числу, n. Галвин (Галвин 1995) разрешил гипотезу, доказав более сильное утверждение, что для любого двудольного графа хроматический индекс и предписанный хроматический индекс равны. Была высказана ещё более общая гипотеза о равенстве хроматического числа и предписанного хроматического числа для произвольных мультиграфов без петель. Эта гипотеза остаётся открытой.

Много изучавшихся вариаций задачи о вершинной раскраске были распространены на рёберную раскраску. Например, задача о полной рёберной раскраске является вариантом полной раскраски, правильной раскраски вершин, при которой любая пара цветов должна присутствовать хотя бы раз в множестве сопряжённых вершин и задача состоит в максимизации общего числа цветов.[24] Строгая рёберная раскраска — это рёберный вариант строгой раскраски[en], при которой любые два ребра со смежными конечными вершинами должны иметь различные цвета.[25] Строгая рёберная раскраска применяется в схеме размещения каналов[en] для беспроводных сетей.[26] Ацикличная рёберная раскраска — это вариант ациклической раскраски, в которой любые два цвета формируют ацикличный подграф (то есть, лес).[27]

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

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

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

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

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

Приложения[править | править вики-текст]

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

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

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

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

Открытые проблемы[править | править вики-текст]

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

  • Гипотеза Голдберга (Голдберг 1973), что хроматический индекс и дробный индекс отличаются не более чем на единицу, что позволило бы аппроксимировать хроматический индекс с ошибкой в один цвет за полиномиальное время.
  • Некоторые гипотезы Якобсена (Jakobsen) и других авторов о структуре критических графов[en] для рёберной раскраски графов класса 2, таких что любой подграф либо имеет меньшую максимальную степень, либо имеет класс 1. Якобсена первоначально предположил, что все критические графы имеют нечётное число вершин, но, в конечном счёте, предположение было опровергнуто. Несколько других гипотез, более слабых чем эта, а также гипотезы, ограничивающие число вершин критических графов и критических мультиграфов, остаются открытыми.
  • Задача Визинга классификации максимальных степеней, что возможно для планарных графов класса 2.
  • Гипотеза о переполненных графах[en] Хилтона (A. J. W. Hilton), утверждающая, что граф со степенью не меньшей n/3 либо имеет класс 1, либо содержит подграф той же степени \Delta, что и исходный граф, а для нечётного числа вершин k, такой что число рёбер подграфа больше \Delta(k - 1)/2. Близка к этой гипотеза Герберта Грёча[en] и Пола Сеймура относительно планарных графов вместо графов высокой степени.
  • Гипотеза Четвинда (Chetwynd) и Хилтона (Hilton) (возможно, имеющая корни в более ранних работах Дирака[en]), что регулярный граф с чётным числом вершин n и степенью как минимум n/2 имеет класс 1.
  • Гипотеза Клауди Бержа[en] и Делберта Фалкерсона[en], что 6-регулярные мультиграфы, образованные удвоением каждого ребра 3-регулярного простого графа без мостов, можно раскрасить шестью цветами.
  • Гипотеза Фьорини и Вилсона, что любые планарные графы без треугольников, отличные от клешни K1,3, не раскрашиваемы рёберно однозначно[en] в 3 цвета.


Из новых гипотез можно упомянуть предположение, что если G является d-регулярным планарным мультиграфом, то G рёберно d-раскрашиваем тогда и только тогда, когда G нечётно рёберно d-связен. Эту гипотезу можно рассматривать как обобщение проблемы четырёх красок для d = 3. Мария Чудновская[en], Катерина Эдвардс (Katherine Edwards) и Пол Сеймур[en] доказали, что 8-регулярный планарный мультиграф имеет рёберное хроматическое число 8.[33]

Замечания[править | править вики-текст]

  1. Soifer, 2008, problem 16.4
  2. Сойфер, 2008
  3. Сойфер 2008, задача 16.5, p. 133. Факт, что нужно либо n, либо (n - 1) цветов следует из теоремы Визинга.
  4. Бигс, 1972
  5. Бигс 1972; Мередит, Ллойд 1973; Бигс 1979.
  6. 1 2 Сойфер 2008, p. 134.
  7. 1 2 Кёниг, 1916
  8. Эрдёш,Уилсон, 1977
  9. Хольер 1981.
  10. Сандерс, Чжао, 2001
  11. Тайт 1880; Аппель, Хакен 1976.
  12. Сойфер 2008, p. 136.
  13. Шеннон, 1949
  14. Бар-Ной, Мотвани, Наор 1992.
  15. Бахмани, Мехта, Мотвани, 2010
  16. Голдберг 1973, Андерсен 1977, Сеймур 1979.
  17. Чен, Ю, Занг, 2011
  18. Эпштейн, 2008
  19. Швенк, 1989
  20. Босак, 1972
  21. Акияма, Икзу, Харари 1980, Хабиб, Пероше 1982, Хорак, Нипель 1982.
  22. Наш-Вильямс, 1964
  23. Габров, Вестерман, 1992
  24. Босак, Нешетрил, 1976
  25. Фуке, Жоливе 1983; Махдиан 2002; Фриз, Кривелевич, Судаков 2005; Крэнстон 2006.
  26. Баррет и др., 2006
  27. Алон, Судаков, Закс 2001, Мутху, Нараянан, Субраманьян 2007.
  28. Эпштейн, 2010
  29. Бурке, Верра, Кингстон, 2004
  30. Скиена, 2008
  31. Вильямсон и др., 1997
  32. Элебах, Дженсен, 2001
  33. (2012-01-13) «Edge-colouring eight-regular planar graphs». Проверено 26 April 2013.

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

  • Jin Akiyama, Geoffrey Exoo, Frank Harary Covering and packing in graphs. III. Cyclic and acyclic invariants // Mathematica Slovaca. — 1980. — В. 4. — Т. 30. — С. 405–417..
  • Noga Alon A simple algorithm for edge-coloring bipartite multigraphs // Information Processing Letters. — 2003. — В. 6. — Т. 85. — С. 301–302. — DOI:10.1016/S0020-0190(02)00446-5.
  • Noga Alon, Benny Sudakov, Ayal Zaks Acyclic edge colorings of graphs // Journal of Graph Theory. — 2001. — В. 3. — Т. 37. — С. 157–167. — DOI:10.1002/jgt.1010.
  • Lars Dovling Andersen On edge-colourings of graphs // Mathematica Scandinavica. — 1977. — В. 2. — Т. 40. — С. 161–175.. Как цитировано у Чен, Ю, Занг 2011.
  • K. Appel, W. Haken Every planar map is four colorable // Bulletin of the American Mathematical Society. — 1976. — В. 5. — Т. 82. — С. 711–712. — DOI:10.1090/S0002-9904-1976-14122-5.
  • Bahman Bahmani, Aranyak Mehta, Rajeev Motwani Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10). — 2010. — С. 31–39..
  • Amotz Bar-Noy, Rajeev Motwani, Joseph Naor The greedy algorithm is optimal for on-line edge coloring // Information Processing Letters. — 1992. — В. 5. — Т. 44. — С. 251–253. — DOI:10.1016/0020-0190(92)90209-E.
  • C.L. Barrett, G. Istrate, V.S.A. Kumar, M.V. Marathe, S. Thite, S. Thulasidasan Proc. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops 2006). — 2006. — С. 106. — ISBN 0-7695-2520-2. — DOI:10.1109/PERCOMW.2006.129.
  • Norman Biggs Research Problems / Richard K. Guy. — American Mathematical Monthly. — 1972. — Т. 79. — С. 1018–1020..
  • Norman Biggs Second International Conference on Combinatorial Mathematics // Annals of the New York Academy of Sciences. — 1979. — Т. 319. — С. 71–81. — DOI:10.1111/j.1749-6632.1979.tb32775.x.
  • Andreas Bjorklund, Thore Husfeldt, Mikko Koivisto Set partitioning via inclusion-exclusion // SIAM Journal on Computing. — 2009. — В. 2. — Т. 39. — С. 546–563. — DOI:10.1137/070683933.
  • Juraj Bosak Chromatic index of finite and infinite graphs // Czechoslovak Mathematical Journal. — 1972. — Т. 22(97). — С. 272–290..
  • Juraj Bosak, Jaroslav Nesetril Complete and pseudocomplete colourings of a graph // Matematicky Casopis Slovenskej Akademie Vied. — 1976. — В. 3. — Т. 26. — С. 171–184..
  • E. Burke, D. De Werra, J. Kingston {{{заглавие}}} / J. L. Gross, J. Yellen. — CRC Press, 2004. — С. 462. — ISBN 978-1-58488-090-5..
  • Guantao Chen, Xingxing Yu, Wenan Zang Approximating the chromatic index of multigraphs // Journal of Combinatorial Optimization. — 2011. — В. 2. — Т. 21. — С. 219–246. — DOI:10.1007/s10878-009-9232-y.
  • Richard Cole, John Hopcroft On edge coloring bipartite graphs // SIAM Journal on Computing. — 1982. — В. 3. — Т. 11. — С. 540–546. — DOI:10.1137/0211043.
  • Richard Cole, Lukasz Kowalik New linear-time algorithms for edge-coloring planar graphs // Algorithmica. — 2008. — В. 3. — Т. 50. — С. 351–368. — DOI:10.1007/s00453-007-9044-3.
  • Richard Cole, Kirstin Ost, Stefan Schirra Edge-coloring bipartite multigraphs in O(E log D) time // Combinatorica. — 2001. — В. 1. — Т. 21. — С. 5–12. — DOI:10.1007/s004930170002.
  • Daniel W. Cranston Strong edge-coloring of graphs with maximum degree 4 using 22 colors // Discrete Mathematics. — 2006. — В. 21. — Т. 306. — С. 2772–2778. — DOI:10.1016/j.disc.2006.03.053.
  • David Eppstein Proc. 16th Int. Symp. Graph Drawing / Ioannis G. Tollis, Marizio Patrignani. — Heraklion, Crete, 2008. — Т. 5417. — С. 78–89. — (Lecture Notes in Computer Science)..
  • David Eppstein Proc. 22nd Canadian Conference on Computational Geometry (CCCG 2010). — 2010..
  • Paul Erdos, Robin J. Wilson Note on the chromatic index of almost all graphs // Journal of Combinatorial Theory. — 1977. — В. 2–3. — Т. 23. — С. 255–257. — DOI:10.1016/0095-8956(77)90039-9.
  • Thomas Erlebach, Klaus Jansen The complexity of path coloring and call scheduling // Theoretical Computer Science. — 2001. — В. 1–2. — Т. 255. — С. 33–50. — DOI:10.1016/S0304-3975(99)00152-8.
  • S. Fiorini, R. J. Wilson Edge-colourings of graphs. — London: Pitman, 1977. — Т. 16. — (Research Notes in Mathematics). — ISBN 0-273-01129-4..
  • Jon Folkman, D. R. Fulkerson Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967). — Chapel Hill, N.C.: Univ. North Carolina Press, 1969. — С. 561–577..
  • J.-L. Fouquet, J.-L. Jolivet Strong edge-colorings of graphs and applications to multik-gons // Ars Combinatoria. — 1983. — В. A. — Т. 16. — С. 141–150..
  • Alan M. Frieze, Michael Krivelevich, Benny Sudakov The strong chromatic index of random graphs // SIAM Journal on Discrete Mathematics. — 2005. — В. 3. — Т. 19. — С. 719–727 (electronic). — DOI:10.1137/S0895480104445757.
  • Harold N. Gabow Using Euler partitions to edge color bipartite multigraphs // International Journal of Computer and Information Sciences. — 1976. — В. 4. — Т. 5. — С. 345–355. — DOI:10.1007/BF00998632.
  • Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daniel Leven, Osamu Terada Algorithms for edge-coloring graphs. — Tohoku University, 1985..
  • Harold N. Gabow, Herbert H. Westermann Forests, frames, and games: algorithms for matroid sums and applications // Algorithmica. — 1992. — В. 5–6. — Т. 7. — С. 465–497. — DOI:10.1007/BF01758774.
  • F. Galvin The list chromatic index of a bipartite multigraph // Journal of Combinatorial Theory. — 1995. — В. 1. — Т. 63. — С. 153–158. — DOI:10.1006/jctb.1995.1011.
  • S. Gandham, M. Dawande, R. Prakash Proc. 24th INFOCOM. — 2005. — Т. 4. — С. 2492–2501. — ISBN 0-7803-8968-9. — DOI:10.1109/INFCOM.2005.1498534.
  • M. K. Gol'dberg Multigraphs with a chromatic index that is nearly maximal // Diskret. Analiz.. — 1973. — В. 23. — С. 3–7, 72.. Как цитировано у Чен, Ю, Занг 2011.
  • M. Habib, B. Peroche Some problems about linear arboricity // Discrete Mathematics. — 1982. — В. 2. — Т. 41. — С. 219–220. — DOI:10.1016/0012-365X(82)90209-6.
  • Ian Holyer The NP-completeness of edge-coloring // SIAM Journal on Computing. — 1981. — В. 4. — Т. 10. — С. 718–720. — DOI:10.1137/0210055.
  • Peter Horak, Ludovit Niepel A short proof of a linear arboricity theorem for cubic graphs // Acta Mathematica Universitatis Comenianae. — 1982. — Т. 40/41. — С. 275–277..
  • Tommy R. Jensen, Bjarne Toft Graph Coloring Problems. — New York: Wiley-Interscience, 1995. — ISBN 0-471-02865-7..
  • Howard J. Karloff, David Shmoys Efficient parallel algorithms for edge coloring problems // Journal of Algorithms. — 1987. — В. 1. — Т. 8. — С. 39–52. — DOI:10.1016/0196-6774(87)90026-5.
  • Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre // Mathematische Annalen. — 1916. — В. 4. — Т. 77. — С. 453–465. — DOI:10.1007/BF01456961.
  • Lukasz Kowalik Improved edge-coloring with three colors // Theoretical Computer Science. — 2009. — В. 38–40. — Т. 410. — С. 3733–3742. — DOI:10.1016/j.tcs.2009.05.005.
  • Mohammad Mahdian On the computational complexity of strong edge coloring // Discrete Applied Mathematics. — 2002. — В. 3. — Т. 118. — С. 239–248. — DOI:10.1016/S0166-218X(01)00237-2.
  • Guy H. J. Meredith, E. Keith Lloyd The footballers of Croam // Journal of Combinatorial Theory. — 1973. — В. 2. — Т. 15. — С. 161–166. — DOI:10.1016/0095-8956(73)90016-6.
  • J. Misra, D. Gries A constructive proof of Vizing's Theorem // Information Processing Letters. — 1992. — В. 3. — Т. 41. — С. 131–133. — DOI:10.1016/0020-0190(92)90041-S.
  • Rahul Muthu, N. Narayanan, C. R. Subramanian Improved bounds on acyclic edge colouring // Discrete Mathematics. — 2007. — В. 23. — Т. 307. — С. 3063–3069. — DOI:10.1016/j.disc.2007.03.006.
  • Crispin Nash-Williams Decomposition of finite graphs into forests // Journal of the London Mathematical Society. — 1964. — Т. 39.
  • George Nemhauser, Sungsoo Park A polyhedral approach to edge coloring // Operations Research Letters. — 1991. — В. 6. — Т. 10. — С. 315–322. — DOI:10.1016/0167-6377(91)90003-8.
  • David A. Richter Proc. 18th International Symposium on Graph Drawing (GD 2010) / Ulrik Brandes, Sabine Cornelsen. — Springer-Verlag, 2011. — Т. 6502. — С. 353–364. — (Lecture Notes in Computer Science). — ISBN 978-3-642-18468-0. — DOI:10.1007/978-3-642-18469-7_32.
  • Daniel P. Sanders, Yue Zhao Planar graphs of maximum degree seven are class I // Journal of Combinatorial Theory. — 2001. — В. 2. — Т. 83. — С. 201–212. — DOI:10.1006/jctb.2001.2047.
  • P. D. Seymour On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte // Proceedings of the London Mathematical Society. — 1979. — В. 3. — Т. 38. — С. 423–460. — DOI:10.1112/plms/s3-38.3.423.
  • Allen J. Schwenk Enumeration of Hamiltonian cycles in certain generalized Petersen graphs // Journal of Combinatorial Theory. — 1989. — В. 1. — Т. 47. — С. 53–59. — DOI:10.1016/0095-8956(89)90064-6.
  • Claude Shannon A theorem on coloring the lines of a network // J. Math. Physics. — 1949. — Т. 28. — С. 148–151..
  • Steven S. Skiena The Algorithm Design Manual. — Springer-Verlag, 2008. — С. 548–550. — ISBN 978-1-84800-069-8. — DOI:10.1007/978-1-84800-070-4_16. Смотрите также [1] в Stony Brook Algorithm Repository.
  • Alexander Soifer The Mathematical Coloring Book. — Springer-Verlag, 2008. — ISBN 978-0-387-74640-1..
  • P. G. Tait Remarks on the colourings of maps // Proc. R. Soc. Edinburgh. — 1880. — Т. 10. — С. 729..
  • Trahtman The road coloring problem // Israel Journal of Mathematics. — 2009. — В. 1. — Т. 172. — С. 51–60. — DOI:10.1007/s11856-009-0062-5 — arΧiv0709.0099.
  • V. G. Vizing On an estimate of the chromatic class of a p-graph // Diskret. Analiz.. — 1964. — Т. 3. — С. 25–30..
  • V. G. Vizing Critical graphs with given chromatic class // Metody Diskret. Analiz.. — 1965. — Т. 5. — С. 9–17.. (На русском.)
  • D. P. Williamson, L. A. Hall, J. A. Hoogeveen, C. A. J. Hurkens, J. K. Lenstra, S. V. Sevast'janov, D. B. Shmoys Short shop schedules // Operations Research. — 1997. — В. 2. — Т. 45. — С. 288–294. — DOI:10.1287/opre.45.2.288.
  • Xiao Zhou, Shin-ichi Nakano, Takao Nishizeki Edge-coloring partial k-trees // Journal of Algorithms. — 1996. — В. 3. — Т. 21. — С. 598–617. — DOI:10.1006/jagm.1996.0061.