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

Вершинной раскраской (далее - просто раскраской) графа называется отображение множества вершин графа на конечное множество (множество цветов); n-раскраска графа - раскраска с использованием n цветов. Раскраска называется правильной, если никакие две вершины одного цвета не смежны. Очевидно, что для графа без петель всегда существует правильная раскраска в |V| цветов.

Хроматическим числом графа G называется минимальное число n=(G), такое, что существует правильная n-раскраска.

Лемма 1. В любом планарном графе без петель и кратных ребер существует вершина степени не более пяти.

Доказательство: допустим, что степени всех вершин превосходят 5. Тогда 2q=Sum(deg(v_i), i=1..|V|)p и q3p. Но по следствию 1 теоремы 2 должно выполняться неравенство q3(p-2)<3p - получили противоречие.

~

Теорема о пяти красках. Каждый планарный граф без петель и кратных ребер является не более чем 5-хроматическим.

Доказательство: (индукцией по числу вершин).

При p=1 утверждение теоремы верно. Допустим, что (*) утверждение верно для всех p<p₀. Докажем, что тогда оно верно и для p₀.

Рассмотрим планарный граф G без петель и кратных ребер с p₀ вершинами; по лемме 1 в нем есть вершина v₀ степени не более 5. По предположению индукции (*) граф G', получаемый удалением из G вершины v₀ (очевидно, также планарный), может быть раскрашен не более, чем в 5 цветов. Пусть (**) v₁...v_k, k=deg(v₀) - все вершины-соседи вершины v₀, расположенные по часовой стрелке относительно v₀. Если в раскраске вершин v₁...v_k используется не более 4-х цветов, то "покрасим" вершину v₀ в оставшийся 5-й цвет и получим правильную раскраску.

Осталось рассмотреть случай, когда в раскраске вершин v₁...v_k в графе G' используется 5 цветов (k=5). Пусть c_i - цвет вершины v_i (i=1..5). Рассмотрим множество A, состоящее из вершины v₁ и всех вершин графа G, исключая v₀, в которые можно дойти из v₁ только по вершинам цветов c₁ и c₃. Возможны два случая:

1. v₃A;

2. v₃A.

В первом случае поменяем цвета вершин множества A (c₁c₃); окраска при этом останется правильной. Действительно, множество A состоит по определению из всех вершин цветов c₁ и c₃, в которые можно дойти из v₁, поэтому среди вершин, смежных вершинам, принадлежащим A, нет вершин цветов c₁ или c₃. После замены цветов вершин множества A вершина v₁ получит цвет с₃, следовательно, можно использовать цвет c₁ для "окраски" вершины v₀ и получить таким образом правильную раскраску графа G.

Остается второй случай. Из принадлежности вершины v₃ множеству A следует, что существует путь из v₁ в v₃ (v₁Sv₃), проходящий только по вершинам цветов c₁ и c₃ (см. рисунок). Рассмотрим цикл L=v₁Sv₃(v₃,v₀)v₀(v₀,v₁)v₁ и замкнутую кривую, которая соответствует этому циклу в геометрической реализации графа. Вершина v₂ находится внутри этой замкнутой кривой, а v₄ - снаружи. Это следует, во-первых, из того, что линии, соответствующие ребрам графа в его геометрической реализации, не могут пересекаться (не считая концов), и, во-вторых, из (**). Определим множество B, состоящее из вершины v₂ и всех вершин графа G, исключая v₀, в которые можно дойти из v₂ только по вершинам цветов c₂ и c₄. Вершина v₄ не принадлежит B, поскольку любой путь из v₂ в v₄ должен проходить, по крайней мере, через одну вершину, принадлежащую циклу L - т.е. либо через вершину v₀, либо через вершину, окрашенную в цвета c₁ или c₃. Следовательно, как и в первом случае, можно поменять цвета вершин множества B (c₂c₄) и "покрасить" v₀ в c₂.

~

Теорема о четырех красках. Каждый планарный граф без петель и кратных ребер является не более чем 4-хроматическим.

Проблема четырех красок оставалась нерешенной в течение многих лет. Утверждается, что эта теорема была доказана с помощью хитроумных рассуждений и компьютерной программы в 1976 году (Kenneth Appel and Wolfgang Haken. Every Planar Map is Four Colorable. Contemporary Mathematics 98, American Mathematical Society, 1980). Краткое изложение идеи их доказательства имеется в [3].