2. Некоторые теоремы и оценки, относящиеся к хроматическим числам

В разд. 4 гл. 3 было введено понятие кликового числа графа (как наибольшего числа вершин в полном порожденном подграфе графа и было отмечено, что поскольку между кликами графа и максимальными независимыми множествами дополнительного графа существует взаимно однозначное соответствие, то справедливы равенства

2.1. Нижние оценки для ...

Очевидно, поскольку по крайней мере цветов требуется для раскраски соответствующей клики графа (той самой клики, которая «определяет» кликовое число графа что является

Рис. Граф

нижней оценкой хроматического числа, т. е.

Более того, Зыков [26] доказал, что эта оценка — точная и что разность может быть сколько угодно большой. В действительности Татт [22] показал, что можно построить граф который не содержит даже полного подграфа третьего порядка (т. е. и который будет иметь произвольно большое заданное значение хроматического числа. На рис. 4.2 изображен граф с и

Поскольку число равно мощности наибольшего множества попарно несмежных вершин графа то оно совпадает также с мощностью наибольшего множества вершин в которые могут быть окрашены в один цвет, и, следовательно,

где число вершин графа обозначает наибольшее целое число, не превосходящее числа х.

Если через обозначить хроматическое число дополнения графа то можно записать следующие два неравенства, полученные Нордхаузом и Гаддумом [19]:

и

где означает наименьшее целое число, которое не меньше х. Еще одна нижняя оценка для предложена Геллером [8]:

Майерс и Лин [18] показали, что оценка из (4.1) равномерно мажорирует приведенную выше, и, следовательно, единственное преимущество оценки (4.5) состоит в том, что ее проще вычислять, чем оценку (4.1).

2.2. Верхние оценки для ...

Нижние оценки хроматического числа безусловно более интересны, чем верхние, поскольку (если они достаточно близки к истинному значению) они могут быть использованы в процедуре вычисления включающей дерево поиска. В то же время верхние оценки хроматического числа подобного применения не находят. Тем не менее в литературе приводятся формулы для вычисления верхних оценок хроматического числа; так Бруксом [3] предложена следующая легко вычисляемая оценка:

Другие достаточно точные верхние оценки, также использующие степени вершин графа, можно найти у Уэлша [23] и Вилфа и Секереша [21].

Верхние оценки, связывающие значения и приводятся у Нордхауза и Гаддума [19]:

и

Оценки, даваемые формулами (4.3), (4.4), (4.7) и (4.8), являются наилучшими в том смысле, что можно построить графы, на которых эти оценки достигаются. В большинстве случаев, однако, они столь неточны, что не имеют никакой практической значимости.

2.3. Гипотеза четырех красок

Граф, который можно так изобразить на плоскости, что никакие два его ребра не пересекаются между собой, называется планарным. Планарные графы важны как с теоретической, так и с практической точек зрения и обладают рядом таких свойств, связанных с раскраской, о которых следует упомянуть.

Теорема о пяти красках [13]

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

«Теорема» о четырех красках (недоказанная)

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

Впервые примерно в 1850 г. о гипотезе четырех красок речь шла в беседах Августа де Моргана и его ученика Гутри. Затем о ней говорилось в письме де Моргана сэру Вильяму Рауэну Гамильтону, датированном 23 октября 1852 г. Поскольку тогда довольно быстро нарастал поток «доказательств», «контрдоказательств», гипотез и теорем, относящихся к этой тематике, то накопилась громадная литература по гипотезе четырех красок, и эта «теорема» стала, по-видимому, самой знаменитой нерешенной задачей в математике. Мы не будем здесь подробно обсуждать гипотезу четырех красок и интересующегося ею читателя отсылаем к замечательной работе Оре [2].