Теорема. Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинаковый цвет.

Раскраска графа

Определение

Раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинаковый цвет.

Определение

Наименьшее возможное число цветов в раскраске называется хроматическим числом графа и обозначается .

Множество вершин покрашенных в один цвет называется одноцветным классом. Одноцветные классы, естественно образуют независимое множество вершин.

Пример

1) для полного графа ;

2) для его дополнения ;

3) для двудольного графа ;

4) для дерева .

Если , то граф называется бихроматическим.

В качестве практического примера рассмотри задачу составления расписания. Предположим нужно прочитать ряд лекций за кратчайшее время. Чтение каждой лекции занимает 1час 20 минут, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же преподаватель). Построим граф, вершины которого – лекции, и две вершины в графе смежны тогда и только тогда, когда лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание. Лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Оптимальное расписание соответствует раскраске с наименьшим числом красок.

Теорема

Пусть G – неориентированный граф без петель, имеющий хотя бы одно ребро. Тогда следующие определения эквивалентны:

1) G – бихроматический граф;

2) G – двудольный граф;

3) G не содержит циклов нечетной длины.

Способы явного выражения хроматического числа через другие числовые характеристики графа неизвестны. Известны лишь некоторые оценки, часть из которых мы рассмотрим.