N-раскраски графов и карт. Хроматическое число графа.

-раскраска графа – это приписывание цветов его вершинам, такое, что две любые смежные вершины окрасятся в разные цвета.

Хроматическим числом графа называется наименьшее число цветов, для которого граф имеет -раскраску. Граф называется -раскрашиваемым, если , и -хроматическим, если .

-раскраска плоской карты – это приписывание цветов его граням, такое, что любые два смежных ребра окрасятся в разные цвета.

Без доказательства приведем следующие факты:

1) Каждый граф 5-раскрашиваем.

2) Гипотеза «каждый граф 4-раскрашиваем» равносильна гипотезе 4 красок «каждая плоская карта 4-раскрашиваема».

В 1976 г К. Аппель и В. Хакен доказали, что четырьмя красками можно раскрасить любую карту. Их доказательство очень объемное, опирается на алгоритмы, реализуемые на компьютерах, в нем все вычисления человеку невозможно проверить.