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

Пусть G = (V, Е) - некоторый граф. Пусть {1, 2,..., k} - множество " цветов". Отображение f: V {1, 2,..., k} называют k-раскраской вершин графа G. К-раскраска называется правильной, если

т.е. смежные вершины получают различную окраску. Граф G называется k-раскрашиваемым, если для него существует правильная k-раскраска. Наименьшее k, для которого граф G является k-раскрашиваемым, называется хроматическим числом графа G (обозначение: x(G)). Если x(G) = k, то граф G называется k-хроматическим.

Существует ряд задач кибернетики, которые приводят к раскраске графа (задачи составления расписаний, обслуживания и др.).

Заметим сначала, что для любого натурального n существует граф G, такой, что x(G)=n. Примером такого графа является К_n. Очевидно, что х(К_n)=n.

Ясно, что 1-хроматические графы это графы, состоящие из изолированных вершин. 2-хроматические графы — это двудольные графы и только они.

В настоящее время нет описания k-хроматических графов при k 3. Нет также эффективных алгоритмов нахождения хроматического числа графа. Однако, имеются хорошие оценки хроматического числа.

Теорема 1. Пусть р - максимальная степень вершин графа G=(V, Е). Тогда справедливо неравенство

x(G) p+l

Индукция по n = |V|. Выберем произвольную вершину v V и удалим ее вместе с инцидентными ей ребрами. Получим граф G', у которого максимальная степень вершин р', причем р' р. Число вершин у G' равно n- 1 и по индукции для G' имеется (р+1)-раскраска, а значит и (р+1)-раскраска. Тогда (р+1) - раскраску для G можно получить так: окрасим v в цвет, отличный от цветов вершин, смежных с ней, число которых не больше р.

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

Теорема 2. Любой планарный граф 6-раскрашиваем.

Заметим сначала, что для связного планарного графа G=(V, Е) выполнено 2m-3f 0.

Это следует из равенств:

По теореме Эйлера должно выполняться n-m+f-2. Отсюда получаем -

3n-m .

Покажем теперь, что в планарном графе существует вершина степени не выше 5.

Пусть напротив, все вершины имеют степень не меньшую, чем 6. Поскольку

deg(v) = 2m, то отсюда следует, что должно быть или .

Два последние неравенства приводят к противоречию. Теперь доказываем утверждение теоремы индукцией по n=|V|. Пусть для всех планарных графов G = (V, Е) с |V| < n₀ утверждение верно. Пусть G - граф с |V| =n₀. По предыдущему, в G есть вершина v степени не выше 5. Удалим v вместе со смежными ей ребрами и получим граф G' с n₀-1 вершинами, планарный. По предположению индукции x(G') G. Пусть v₁,..., v_k - вершины G', смежные с v. Имеем k 5. Для раскраски G используем для v цвет, отличный от цветов v₁,..., v_k. Следовательно, x(G) G.

Усложнив рассуждения, можно доказать, что x(G) 5 для всякого планарного графа. Гипотеза 4^х красок для планарного графа была сформулирована А. Кэли в 1878 году и утверждала, что x(G) = 4.

Данная гипотеза была подтверждена в 1978 году Аппелем Т. и Хакеном М. Соответствующее доказательство использовало компьютер и пока оно не имеет проверки в традиционном понимании.