Глава 4. РАСКРАСКИ
1. Введение
Разнообразные задачи, возникающие при планировании производства, составлении графиков осмотра, хранении и транспортировке товаров и т. д., могут быть представлены часто как задачи теории графов, тесно связанные с так называемой «задачей раскраски». Графы, рассматриваемые в этой главе, являются неориентированными и не имеют петель; если специально не оговаривается иное, то под словом «граф» понимается именно такой граф.
Граф 
называют 
-хроматическим, если его вершины могут быть раскрашены с использованием 
цветов (красок) так, что не найдется двух смежных вершин одного цвета. Наименьшее число 
такое, что граф 
является 
-хроматическим, называется хроматическим числом графа 
и обозначается 
Задача нахождения хроматического числа графа называется задачей о раскраске (или задачей раскраски) графа. Соответствующая этому числу раскраска вершин разбивает множество вершин графа на 
подмножеств, каждое из которых содержит вершины одного цвета. Эти множества являются независимыми, поскольку в пределах одного множества нет двух смежных вершин.
Вообще говоря, хроматическое число графа (так же как числа независимости и доминирования, рассмотренные в предшествующей главе) нельзя найти, зная только числа вершин и ребер графа. Недостаточно также знагь степень каждой вершины, чтобы вычислить хроматическое число графа. В этом можно убедиться, рассматривая графы, приведенные на рис. 4.1(a) и 4.1(б). Эти графы имеют по 
вершин, 
ребер и одинаковые распределения степеней вершин 
Однако хроматические числа данных графов равны 4 и 2 соответственно. При известных величинах 
(число вершин), 
(число ребер) и 
(степени вершин графа) можно получить верхнюю и нижнюю оценки для хроматического числа графа. Этим оценкам посвящен следующий раздел.
Задача нахождения хроматического числа произвольного графа явилась предметом многих исследований в конце XIX и в текущем столетии. Сейчас по этому вопросу известно большое количество интересных результатов. В этой главе, однако, мы не пытаемся обсудить эти результаты или хотя бы дать их краткий обзор. Мы вводим только такие понятия, которые нужны для построения
Рис. 4.1. Два графа с одинаковыми 
и распределениями степеней вершин, но с различными хроматическими числами, 
алгоритмов решения задачи о раскраске графа. Здесь мы рассматриваем в основном алгоритмы (как точные, так и «приближенные»), позволяющие находить (точное или приближенное) значение хроматического числа произвольного графа и соответствующую этому значению раскраску вершин.
