9.3. Реберная раскраска и хроматический индекс

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

Не нарушая общности, допустим, что графы, рассматриваемые в этом разделе, не имеют петель.

Хроматический индекс или реберное хроматическое число графа G — это минимальное число k, для которого граф G имеет правильную реберную -раскраску. Граф G называется реберно -хроматическим, если Хроматический индекс графа на рис. 9.3, а равен 4.

Легко видеть, что реберная -раскраска графа влечет разбиение множества Е, где подмножество ребер, которым присвоен в раскраске цвет i. Аналогично любое разбиение множества Е на k подмножеств соответствует реберной -раскраске графа G.

Рис. 9.3. Реберная раскраска (числа помечают цвета). а — правильная реберная -раскраска; б — реберная -раскраска.

Поэтому мы часто будем обозначать реберную раскраску соответствующим разбиением графа

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

Поскольку в любой правильной раскраске ребра, инцидентные одной вершине, получают разные цвета, то

где А — максимальная степень в графе G. В общем случае однако в случае двудольных графов

Теорема 9.6. Для двудольного графа .

Доказательство. Согласно следствию 8.22.1, множество ребер двудольного графа G можно разбить на Д паросочетаний. Следовательно, Объединение этого неравенства с выражением (9.6) доказывает теорему.

Хотя в общем случае А цветов недостаточно для того, чтобы правильно раскрасить ребра графа, Визинг [9.4] показал, что для любого простого графа достаточно цветов. Для доказательства теоремы Визинга нам необходимо установить несколько основных результатов.

Будем говорить, что цвет i представлен в раскраске в вершине v, если хотя бы одному ребру, инцидентному вершине v, присвоен цвет . Число различных цветов, представленных в вершине v, будем обозначать через Например, в раскраске, показанной на рис. 9.3, б, .

Теперь рассмотрим вопрос о существовании реберной -раскраски графа, в котором для каждой вершины v графа.

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

Доказательство.

Случай 1. Граф G—эйлеров.

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

Если G — не цикл, тогда он должен иметь вершину степени не менее 4, Пусть — эйлерова цепь и

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

Случай 2. Граф G — не эйлеров.

В этом случае граф G должен иметь четное число нечетных вершин. Построим сейчас эйлеров граф G, добавляя новую вершину и соединяя ее в графе G с каждой вершиной нечетной степени. Пусть — эйлерова цепь в графе G. Если определены, как в выражении (9.7), то есть реберная -раскраска графа G, в котором оба цвета представлены в каждой вершине графа G. Сейчас легко видеть, что является реберной -раскраской графа G, в котором оба цвета представлены в каждой вершине степени не менее 2.

Реберная -раскраска графа называется оптимальной, если не существует другой такой реберной -раскраски графа G, что

где — числа различных цветов, представленных в вершине v в раскрасках и S соответственно. Очевидно, что в любой раскраске для каждой вершины V. Более того, для каждой вершины v равенство справедливо тогда и только тогда, когда — правильная раскраска. Следующий полезный результат раскрывает природу оптимальной раскраски.

Лемма 9.4. Пусть — оптимальная -раскраска графа . Допустим, что в графе G существуют вершина и и такие два цвета i и j, что I не представлен в и, a j представлен в и дважды. Пусть G — порожденный подграф графа G на множестве ребер Тогда компонента Я графа G, содержащая вершину и, является циклом нечетной длины.

Доказательство. Если Н не является циклом нечетной длины, то, согласно лемме 9.3, существует реберная -раскраска, в которой цвета i и представлены в каждой вершине Н степени не менее 2.

Если мы используем эту реберную -раскраску для перекраски ребер компоненты Н и оставим цвета других ребер графа G без изменения, тогда получим новую реберную -раскраску в которой цвета будут представлены в

вершине . Следовательно, с где с число различных цветов, представленных в вершине и в раскраске Кроме того, для каждой вершины Следовательно, что противоречит оптимальности реберной раскраски ?. Таким образом, Н — цикл нечетной длины. Реберная -раскраска называется улучшением реберной -раскраски если

Сейчас мы докажем теорему Визинга [9.4]. Используемое нами доказательство предложено Фурнье [9.5]. В его изложении будем следовать Бонди и Мурчи [9.6].

Рис. 9.4.

Теорема 9.7 (Визинг). Если простой граф, то либо либо

Доказательство. Поскольку будет достаточно, если мы докажем, что

Пусть — оптимальная реберная (-раскраска графа G. Допустим, что — неправильная реберная (-васкраска. Тогда в графе G существует такая вершина и, что ). Отсюда

следует, что существуют такие цвета что не представлен в вершине и, а представлен в ней дважды. Пусть ребро имеет цвет .

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

Предположим, что в вершине не представлен цвет (3. Тогда он должен быть представлен в вершине и, в противном случае мы можем перекрасить ребро в цвет а ребро получая улучшение раскраски Пусть ребро имеет цвет

Повторяя эти рассуждения, можно построить такие последовательности вершии и цветов имеет цвет не представлен в вершине

Легко видеть, что существует такое наименьшее целое число I, что для некоторого справедливо равенство (рис. 9.4, а).

Для получения противоречия перекрасим теперь двумя разными способами некоторые ребра, инцидентные и, и получим две новые оптимальные реберные (-раскраски:

Раскраска получается перекраской ребра в цвет Каждое из оставшихся ребер графа G получает в раскраске тот же цвет, что и в раскраске (рис. 9.4, б).

Раскраска получается перекраской ребра в цвет а ребра — в цвет Каждое из оставшихся ребер графа G получает в раскраске ?” тот же цвет, что и в раскраске (рис. 9.4, в).

Пусть G — подграф графа G на множестве ребер ), его компонента, содержащая вершину и. Аналогично G" — подграф графа G на множестве ребер а — его компонента, содержащая вершину и.

Как в раскраске так и в цвет не представлен в вершине и, а цвет представлен в этой вершине дважды. Поэтому из леммы 9.4 следует, что — циклы.

Единственным ребром цикла , которого нет в цикле является ребро . Поэтому вершины и и связаны также и в подграфе Следовательно, они лежат в одной и той же компоненте подграфа а именно в компоненте Тогда степень в Я" равна 1, иначе бы степень ее в была больше 2. Это противоречит тому, что — также цикл. Таким образом, — правильная реберная (-раскраска.

Более общий результат по сравнению с выводом этой теоремы можно найти в упражнении 9.8.