Раскраска вершин графа

Пусть задан абстрактный граф G (V, E). Говорят, что вершины графа G правильно раскрашены, если каждой вершине присвоен определенный цвет, причем любым двум смежным вершинам присвоены разные цвета. Если вершины графа правильно раскрашены, то ребра могут соединять лишь вершины разного цвета. Так как петля соединяет некоторую вершину с собой, то невозможно правильно раскрасить граф, содержащий хотя бы одну петлю. Граф без петель (т.е. мультиграф) называется р-хроматическим, если он допускает правильную раскраску вершин в р цветов. Наименьшее значение р, при котором граф G является р-хроматическим, называется хроматическим числом графа G. Если граф имеет параллельные ребра, то это обстоятельство не увеличивает числа необходимых цветов для правильной раскраски его вершин. Поэтому задачу о нахождении хроматического числа графа достаточно уметь решать лишь для элементарных графов. Ясно, что хроматическое число элементарного графа не превышает количества его вершин и совпадает с числом вершин, если граф является полным.

Легко видеть, что хроматическое число графа равно единице тогда и только тогда, когда граф не содержит ни одного ребра. Найдем геометрическую интерпретацию хроматического числа графа, если число его ребер больше единицы. Предположим сначала, что граф является 2- хроматическим и его вершины раскрашены в два цвета а и Р. Разобьем множество вершин V графа G на два подмножества V_a и Vp в зависимости от их цвета. По определению 2-хроматичности, ни одна вершина из подмножества V_a не может быть смежна ни одной вершине из Vp. Следовательно, граф G является двудольным. Обратно, если граф G является двудольным, то раскрашивая вершины из первой «доли» в один цвет, а вершины из второй «доли» в другой, мы получим правильную раскраску вершин графа. Итак, граф является 2-хроматическим тогда и только тогда, когда он является двудольным. В силу этого обстоятельства двудольные графы называют также бихроматическими. Аналогично, граф является р-хроматическим тогда и только тогда, когда он является р-дольным. Следовательно, хроматическое число графа можно определить как наименьшее значение для р, при котором граф является р-дольным.

Используя известное свойство двудольных графов, можно сформулировать также следующий признак 2-хроматичности: граф является 2-хроматическим тогда и только тогда, когда он не содержит циклов нечетной длины.

Определение хроматического числа абстрактного графа общего вида является достаточно сложной задачей. В этой связи уместно упомянуть следующий результат, полученный Р. Бруксом: пусть в элементарном графе G степень каждой вершины не больше р (р>2), и граф не содержит компоненты связности, являющейся полным графом с р+] вершинами, тогда граф G является рхроматическим.

Рассмотрим теперь некоторый плоский граф G (V, E, F) и поставим задачу о правильной раскраске его вершин. Мы знаем, что каждому плоскому графу соответствует его плоский двойственный граф G'(V', E', F'). Так как при двойственном отображении вершины графа G переходят в грани графа G', а грани графа G переходят в вершины графа G', и это отображение сохраняет отношение смежности, то задача о правильной раскраске вершин плоского графа G эквивалентна задаче о правильной раскраске граней двойственного графа G'. Поэтому, используя соображения двойственности, мы можем легко получить теоремы о пяти, двух и трех красках, относящиеся к вопросу правильной раскраски вершин плоского графа.

Теорема 19 (двойственная теореме 16). Любой плоский граф допускает правильную окраску вершин в пять цветов.

Теорема 20 (двойственная теореме 17). Для того чтобы плоский граф допускал правильную окраску вершин в два цвета, необходимо и достаточно, чтобы каждая грань этого графа была ограничена четным числом ребер.

Теорема 21 (двойственная теореме 18). Для того чтобы плоская триангуляция допускала правильную окраску вершин в три цвета, необходимо и достаточно, чтобы каждая ее вершина была четной.