назад

3.9 Раскраска графов

1. Говорят, что вершины (соответственно ребра) неориентированого графа G без петель правильно раскрашены, если каждой вершине (соответственно каждому ребру) графа сопоставлен ровно один из заданного набора цветов, причем любым двум соседний вершинам (соответственно смежным ребрам) сопоставлены разные цвета. Граф, вершины или ребра которого правильно раскрашен будем называть правильно раскрашенным, если из контекста ясно какие именно элементы графа раскрашиваются или это безразлично. Очевидно, что всякий подграф правильно раскрашенного графа также правильно раскрашен. Удобно нумеровать цвета натуральными числами 1, 2,.... Отрезок натурального ряда от 1 до k включительно будем обозначать Nk. Можно сказать, что правильная раскраска вершин (соответственно ребер) графа - это функция с натуральными, значениями, определенная на множестве вершин (соответственно ребер) и разнозначная на концах каждого ребра (соответственно на ребрах каждой звезды) графа.

Основная задача состоит в определении наименьшего числа (G) (соответственно '(G)) различных цветов, с помощью которых можно правильно раскрасить вершины (соответственно ребра) графа G. (G) называется хроматическим числом, a '(G) - хроматическим классом графа G.

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

Очевидно, что для всякого графа с b вершинами (G) ≤ b, причем равенство достигается только для полного графа: всякий другой граф можно раскрасить меньшим числом цветов, окрасив две несмежные вершины одинаково. С другой стороны, если в графе имеется хотя бы одно ребро, (G) 2.

Графы, для которых (G)= 2, называются бихроматическими. Ясно, что бихроматический граф является двудольным, и наоборот всякий двудольный граф, содержащий хотя бы одно ребро, бихроматичен. Справедливо и другое условие бихроматичности и тем самым двудольности графа.

Теорема. Для того чтобы граф, содержащий хотя бы одно ребр был бихроматическим, необходимо и достаточно, чтобы он не содержал элементарных циклов нечетной длины.

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

Достаточность. Заметим прежде всего, что дерево бихроматично. В самом деле, выберем произвольно корень и используем представление дерева, описанное в параграфе 3. Окрасим все вершины четных ярусов в один цвет, а все вершины нечетных ярусов в другой цвет. Эта раскраска правильная, так как ребра в дереве соединяют только вершины соседних ярусов.

Рассмотрим теперь элементарную цепь, соединяющую в дереве вершину i-гo яруса и вершину j-гo яруса. На каждом ее ребре происходит изменение номера яруса на единицу. Поэтому ее длина имеет ту же четность, что и число i - j. В частности, вершины, принадлежащие ярусам одинаковой четности, связаны элементарной цепью четной длины.

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

3. Если граф содержит в качестве подграфа t-вершинный полный граф Kt, то его хроматическое число, очевидно, не меньше t. Противоположное утверждение, однако, неверно. Существуют графы даже без треугольников К3, имеющие сколь угодно большое хроматическое число. Пример такого графа с хроматическим числом 4 приведен на рисунке 19


Рисунок 19

Рассмотрим, как связано хроматическое число со степенями вершин графа. Обозначим через s(G) максимальную из степеней вершин графа G, а через Г(s) - класс графов без кратных ребер, для которых s(G) ≤ s. Нетрудно показать индукцией по числу вершин, что если G Г(s), то (G) ≤ s + 1. В самом деле, если число вершин в графе меньше или равно (s + 1), то утверждение тривиально. Пусть теперь оно установлено для всех графов из Г(s), имеющих меньше вершин, чем граф G. Удалим из G звезду произвольной вершины и β соответствии с предположением индукции правильно раскрасим граф G\Z(s + 1) цветами. В графе G у вершины не более s соседних вершин, поэтому в множестве цветов Ns+1 есть хотя бы один цвет, которым не окрашена ни одна из вершин, соседних с . Его можно использовать для окраски вершины , после чего граф G будет правильно раскрашен (s + 1) цветами.

Полный (s + 1)-вершинный граф Ks+1 представляет собой пример графа из Г(s), для которого хроматическое число равно s + 1. Оказывается, что этот пример - единственный, а именно справедлива следующая теорема

Теорема. Пусть s3. Если G Г(s) и GKs+1, то (G)≤s.

 

Вопросы для самоконтроля

  1. Дайте определение хроматического класса графа G.
  2. Дайте определение бихроматического графа.
  3. Сформулируйте и докажите основные теоремы раздела.