Точный алгоритм раскрашивания

1) выбрать в графе G некоторое максимальное независимое множество вершин S.

2) Покрасить множество вершин S в некоторый очередной цвет.

3) Применить процедуру для графа G\S.

Алгоритм продолжаем до тех пор пока не получим пустой граф.

Приближенный алгоритм последовательной раскраски

Данный алгоритм во многих случаях приводит к раскраскам близким к оптимальным.

1) Выбираем произвольную вершину графа G - и красим ее в цвет 1.

2) Если вершины раскрашены m цветами m< =i, то новой произвольно взятой вершине приписываем минимальный цвет, не использованный при раскраске вершин из множества

Пример

1 1-1 4-2

4 5 2-1 5-3

6 3-2 6-1

2 3

Раскраска планарных графов

Еще в 1840 году возникла задача четырех красок. Она состоит в том, что можно ли раскрасить карту так, что никакие две смежные области не были бы выкрашены в один цвет.

Делалось много попыток решения этой задачи, некоторые из которых были ошибочны. Последние попытки доказательства (американские ученые Аппель и Жани) - это доказательство с использованием компьютера (частично конструктивное). При этом оговаривалось максимальное число вершин графа. В последнее время четырехраскрашиваемость доказана для графов с числом вершин 96. Почему не доказано для большего числа вершин? Доказательство занимает очень много времени. Для данного варианта это заняло 1500 часов.

Строго доказана для планарных графов лишь теорема о пяти красках.