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

Рассмотрим вначале нижние оценки для c(G).

Начнем с оценки, связанной с плотностью графа.

Определение. Плотностью j(G) графа G называется наибольшее число вершин полного подграфа графа G.

Следующее утверждение очевидно.

Предложение 1. Для любого графа G выполняется неравенство

j(G) ≤ c(G).

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

Теорема 5.2. Для всякого k ≥ 2 существует граф G такой, что j(G)=2 и c(G)=k.

Доказательство. Для связного не одноэлементного графа G равенство j(G)=2 означает, что G не содержит треугольников, т.е. трехэлементных полных графов. Индуктивно построим последовательность G₂,G₃,…,G_k,… графов без треугольников, для которых c(G_k)=k.

Положим G₂=K₂. Предположим, что граф G_k=(V_k,E_k) уже построен и V_k={v₁,v₂,…,v_n}. Пусть V_k′={v₁′,v₂′,…,v_n′}, V_kÇV_k′=Æ и vÏV_kÈV_k′. Множество вершин графа G_k+1 будет равно V_kÈV_k′È{v}.Множество ребер этого графа получается добавлением к E_k ребер, соединяющих вершину v_i′ c вершинами из V_k, которым смежна v_i в графе G_k, и ребер, соединяющих v со всеми вершинами из V_k′. Переход от G₂ к G₃ показан на рис. 5.5, а переход от G₃ к G₄ – на рис. 5.6.

Докажем, что G_k+1 не содержит треугольников. Действительно, треугольник не может содержать вершину v, поскольку она смежна только вершинам V’, которые попарно не смежны. По той же причине треугольник не может содержать две вершины из V′. Если же в графе G_k+1 попарно смежны вершины v_i′, v_p, v_q, то в G_k попарно смежны вершины v_i, v_p, v_q. Поскольку по предположению индукции в G_k нет треугольников, то и в G_k+1 нет треугольников.

Проверим, что c(G_k+1)=k+1. Пусть

f: V_k®{1,2,…,k} –

правильная раскраска графа G. Продолжим функцию f на V_k′È{v} следующим образом: f(v_i′)=f(v_i), f(v)=k+1. Мы получим правильную раскраску графа G_k+1 (k+1) краской. Следовательно, c(G_k+1) ≤ k+1. Предположим, что G_k+1 можно правильно раскрасить k красками. Тогда вершины из V_k′ раскрашены не более, чем k-1 краской, поскольку одна краска израсходована на вершину v. Если перекрасить вершины из V_k следующим образом: вершину v_i покрасить той же краской, что и v_i′, то мы получим правильную раскраску графа G_k не более, чем k-1 красками. Полученное противоречие доказывает, что граф G_k+1 нельзя правильно раскрасить k красками. Таким образом, X(G_k+1)=k+1.

Теорема доказана.

Вторая оценка использует число независимости графа.

Определение. Множество попарно несмежных вершин графа называется независимым множеством. Числом независимости b(G) графа G называется наибольшее число вершин независимого множества.

Так для графов G₁ и G₂, изображенных на рис.5.1, получаем, что b(G₁)=3, b(G₂)=2.

Предложение 2. Для любого графа G выполняется неравенство

n/b(G)£c(G

Доказательство. Пусть c(G)=k. Тогда при оптимальной раскраске графа G множество V разбивается на k классов V₁,V₂,…,V_k одинаково раскрашенных вершин. Каждое из множеств V_i является независимым и поэтому ½V_i½£b(G). Тогда

n=½V₁½+½V₂½+…+½V_k½£kb(G).

Следовательно, n/b(G)£k.

Разность c(G) - n/b(G) тоже может быть сколь угодно большой, как и в первом случае. Только установить это можно гораздо проще. Пусть Н – полный граф с множеством вершин V={v₁,v₂,…,v_k}. Добавим к V еще k новых вершин v₁′,v₂′,…,v_k′ и k новых ребер, соединяющих вершины v_i′ и v_i для 1£i£k. Полученный граф обозначим буквой G. Легко видеть, что c(G)=k, a n/b(G)=2.

Нижние оценки хроматического числа в предложениях 1 и 2 обладают еще одним недостатком: задача вычисления чисел j(G) и b(G) столь же сложна, как и задача вычисления хроматического числа. (Это утверждение здесь мы пояснять не будем, подробно о сложности задач см. в книге Гэри и Джонсона .)

Известны нижние оценки хроматического числа, использующие «легко вычисляемые» величины. Укажем одну из них.

Предложение 3. Для любого графа G выполняется неравенство

n²/(n² – 2m) £ c(G).

Отметим, что для полного графа 2m=n(n-1), поэтому для произвольного графа n²–2m>0. (По поводу доказательства предложения 3 см. книгу Н. Кристофидеса, стр.78.)

Из верхних оценок укажем одну, приведенную в теореме 5.3, которую часто называют теоремой Брукса. (Теорема доказана Бруксом в 1941г.) Через D(G) обозначим наибольшую степень вершин графа G.

Теорема 5.3. Пусть G=(V,E) – связный неполный граф и D(G)³3. Тогда c(G)£D(G).

Доказательство. В силу теоремы можно считать, что G – двусвязный граф.

Докажем вначале, что в G существуют (различные) вершины u и v такие, что d(u,v)=2 и граф G–u–v является связным. Обозначим через D множество доминирующих вершин графа, т.е. таких вершин, что любая другая вершина смежна с этой вершиной. Если вершинная связность k(G) больше или равна трех или D¹Æ, то существование указанных вершин u и v достаточно очевидно. Действительно, поскольку G неполный граф, то в нем найдутся вершины u и v такие, что d(u,v)=2. Если k(G)³3, то их удаление не нарушит связности графа. (Напомним, что k(G) – наименьшее количество вершин, удаление которых нарушает связность.) Эти вершины не принадлежат D, поэтому если D¹Æ, то в графе G–u–v найдется доминирующая (в нем) вершина. Отсюда следует, что граф G–u–v является связным и d(u,v)=2.

Будем считать, что k(G)<3 и D=Æ. Поскольку G не содержит точек сочленения, то из неравенства k(G)<3 следует равенство k(G)=2. Возьмем вершину х для которой r(x)³3. Такая вершина существует, поскольку D(G)³3.

Рассмотрим граф G’=G – x. Так как k(G)=2, то G’ – связный граф. Если k(G’)=2, то в качестве u возьмем х, а в качестве v – вершину графа G, находящуюся от х на расстоянии 2. (Такая вершина v существует, поскольку D=Æ.)

Предположим теперь, что k(G’)=1, т.е. что граф G’ содержит (хотя бы одну) точку сочленения. Пусть В – концевой блок графа G’ и а – точка сочленения графа G, принадлежащая этому блоку. Тогда вершина х смежна хотя бы с одной вершиной блока В, отличной от а. Поскольку в противном случае точка а будет точкой сочленения графа G (см. рис. 5.7, где прямоугольниками изображены блоки графа G – х).

Рис.5.7

Возьмем два концевых блока В и С графа G – х и в блоках В и С точки u и v, смежные с х. Поскольку u и v не смежны, то d(u,v)=2. Легко видеть, что граф G – u – v связен. Действительно, графы B – u и C – v являются связными, а поэтому граф G – u – v – x является связным. Но r(х)³3 и поэтому граф G – u – v также связный.

Итак, в G существуют вершины u,v такие, что d(u,v)=2, вершины u и v смежны с вершиной х и граф G – u – v является связным. Упорядочим вершины графа G – u – v следующим образом. На первое место поставим вершину х₁, на второе – одну из смежных с х вершин (напомним, что в графе G r(х)³3). Предположим, что мы упорядочили i вершин графа G – u – v и получили последовательность: x₁,x₂,…,x_i. Среди оставшихся вершин графа G – u – v найдется вершина w, которая смежна одной из вершин x₁,…,x_i, поскольку G – u – v связный граф. Положим x_i+1=w. В результате мы получим последовательность x₁,…,x_n-2 графа G – u – v такую, что каждая вершина x_i (1£i£n-2) смежна хотя бы одной вершине с меньшим номером.

Для удобства обозначим D(G) буквой k и раскрасим граф G k красками следующим образом. Вершины u и v покрасим первой краской. Вершины графа G – u – v расположены в указанную выше последовательность x₁,x₂,…,x_n-2. Эти вершины раскрашиваем, начиная с x_n-2. Вершину x_n-2 раскрасим первой краской, если она не смежна u и v, и второй, если x_n-2 смежна одной из этих вершин. Предположим, что вершина x_i (2<i£n-2) уже раскрашена. Тогда, поскольку r(x_i-1)£k и x_i-1 смежна хотя бы одной вершине с меньшим номером, то для раскраски вершин, смежных с x_i-1, израсходовано менее k красок. Следовательно, осталась краска для x_i-1. Итак, все вершины графа G, кроме х₁, раскрашены. Так как х₁ смежна вершинам u и v, раскрашенным одной краской и r(х₁)£k, то для раскраски вершин, смежных х₁, израсходовано менее k красок. Это означает, что осталась краска для х₁. В итоге мы получаем правильную раскраску графа G.

Теорема доказана.

Верхняя оценка хроматического числа, даваемая теоремой Брукса, является удовлетворительной для тех графов, степени вершин которых примерно одинаковы. В общем же случае разность между D(G) и c(G) может быть сколь угодно большей. Рассмотрим граф, изображенный на рис. 5.8. Очевидно, что c(G)=2 и в то же время, D(G)=l.

Рис.5.8

Итак, общий итог «изысканий», проведенных в первом и втором параграфах, можно назвать неутешительным. Как мы видели, не существует формулы, позволяющей вычислить хроматическое число по «знакомым» величинам: число вершин, ребер, компонент связности, степени вершин, и нет достаточно хороших оценок для хроматического числа. Эта ситуация является отражением того факта, что задача вычисления хроматического числа является трудно решаемой, так же, как и задача нахождения гамильтонова цикла. Обсуждение алгоритмов вычисления хроматического числа выходит за рамки данного пособия, и мы ограничимся лишь тем, что приведем простой алгоритм нахождения правильной раскраски, близкой к оптимальной.

Алгоритм состоит в следующем. Упорядочиваем вершины графа G: V={v₁,v₂,…,v_n}.Вершину v₁ красим первой краской. Предположим, что вершины v₁,…,v_i уже раскрашены и на это использовано l красок. Если на раскрашенные вершины, смежные с v_i+1, использованы все краски, то v_i+1 раскрашиваем l+1 краской. Если среди l красок найдется краска, которая не использована для вершин, смежных с v_i+1, то вершину v_i+1 красим этой краской.

Приведенный алгоритм часто называют алгоритмом последовательной раскраски. Нетрудно привести примеры, когда такая раскраска не является оптимальной.