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

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

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

Рёбра полного графа с вершинами могут быть раскрашены цветами, если чётно. Это специальный случай теоремы Бараньяи. Сойфер даёт следующее геометрическое построение раскраски в этом случае: разместим точек в углах и в центре правильного -угольника. Для каждого класса цвета выберем одно ребро, соединяющее центр и одну из вершин многоугольника, и все перпендикулярные ему рёбра, соединяющие пары вершин многоугольника. Однако если нечётно, требуется цветов — каждый цвет можно использовать только для раскраски рёбер, -ю часть всех рёбер, задача 16.5, p. 133. Факт, что нужно либо , либо цветов следует из теоремы Визинга..

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

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

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

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

Связь с паросочетаниями

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

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

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

Связь со степенью

Теорема Визинга Рёберное хроматическое число графа тесно связано с максимальной степенью (максимальное число рёбер, инцидентных любой отдельной вершине графа ). Ясно, что , так что если различных рёбер содержат вершину , то все эти рёбра должны быть раскрашены в различные цвета, что возможно только если имеется как минимум цветов. Теорема Визинга (названа в честь Вадима Визинга, опубликовавшего её в 1964 году) утверждает, что эта граница почти точна — для любого графа рёберное хроматическое число равно либо , либо . Если , говорят, что G имеет класс 1, в противном случае говорят о классе 2.

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

Визинг доказал, что планарные графы максимальной степени не менее восьми имеют класс 1 и высказал гипотезу, что то же самое верно для планарных графов степени 7 или 6. С другой стороны, существуют планарные графы с максимальной степенью от двух до пяти, имеющие класс 2. С тех пор гипотеза доказана для семи. Планарные графы без мостов, Кубические графы имеют класс 1, и это равносильно формулировке задачи о четырёх красках; ..

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

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

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

Мультиграфы

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

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

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

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

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