Хроматическое число

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Раскрашиваемый граф»)
Перейти к навигации Перейти к поиску
Пример раскраски графа Петерсена. Для раскраски этого графа достаточно 3 разных цвета, его хроматическое число равно 3.

Хромати́ческое число графа — минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета.

Формально, хроматическое число — минимальное число , такое что множество вершин графа можно разбить на непересекающихся классов :

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

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

Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырёх красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырёх красок, гипотеза Хадвигера.

Рёберная раскраска[править | править код]

реберная раскраска кубического графа

Хроматический класс графа  — минимальное число цветов, в которые можно раскрасить ребра графа так, чтобы смежные ребра имели разные цвета. Обозначается . Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырёх красок. Рёберная раскраска определяет 1-факторизацию графа.

Хроматический многочлен[править | править код]

Если рассмотреть количество различных раскрасок помеченного графа как функцию от доступного числа цветов , то оказывается, что эта функция всегда будет полиномом от . Этот факт был обнаружен Биркгофом и Льюисом[1] при попытке доказать проблему четырёх красок.

Хроматические многочлены некоторых графов:

Треугольник
Полный граф
Дерево с вершинами
Цикл
Граф Петерсена

Для графа-вершины хроматический многочлен равен :

Хроматический многочлен графа равен произведению хроматических многочленов его компонент:

Также существует рекуррентное соотношение — теорема Зыкова[2], так называемая формула удаления и стягивания

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

где и  — несмежные вершины, а  — граф, получающийся из графа путём добавления ребра

Для всех целых положительных выполнено . Хроматическое число  — наименьшее целое положительное , для которого . Степень хроматического многочлена равна количеству вершин — .

Обобщения[править | править код]

Также хроматическое число можно рассматривать для других объектов, например, для метрических пространств. Так, хроматическим числом плоскости называется минимальное число цветов , для которого существует такая раскраска всех точек плоскости в один из цветов, что никакие две точки одного цвета не находятся на расстоянии ровно 1 друг от друга. Аналогично для любой размерности пространства. Элементарно доказывается, что для плоскости , однако продвинуться дальше долгое время не удавалось. 8 апреля 2018 года, британский математик Обри ди Грей доказал, что [3][4]. Эта задача называется задачей Нелсона — Эрдёша — Хадвигера.

Кроме того, множество вершин произвольного графа  может быть рассмотрено как метрическое пространство, в котором расстояния между смежными вершинами равны , а все остальные ненулевые расстояния равны , где  — произвольные фиксированные вещественные числа.  — метрическое пространство, состоящее из точек, удалённых друг от друга на расстояние . В этом случае имеет место следующий результат (Иванов — Тужилин, 2019[5]): если  — наибольшее натуральное число, для которого ( — расстояние Громова — Хаусдорфа между и ; если таких натуральных чисел не существует, то считается ), то . Хроматическое число равно , если и только если граф не содержит ни одного ребра. В этом случае равенство не выполняется ни для какого , поэтому, в силу сделанного соглашения, , что приводит к верному равенству . По определению не превосходит количества элементов множества . С другой стороны, несложно показать, что при каждом , поэтому и, значит, .

Примечания[править | править код]

  1. Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.
  2. Этот домен припаркован компанией Timeweb. Дата обращения: 4 июня 2017. Архивировано 28 мая 2017 года.
  3. de Grey, Aubrey D.N.J (2018-04-08), The chromatic number of the plane is at least 5, arXiv:1804.02385
  4. Владимир Королёв. Математикам не хватило четырех цветов для раскраски плоскости. nplus1.ru. Дата обращения: 11 апреля 2018. Архивировано 10 апреля 2018 года.
  5. A. O. Ivanov, A. A. Tuzhilin (2019), The Gromov-Hausdorff Distance between Simplexes and Two-Distance Spaces (PDF), arXiv:1907.09942 Архивная копия от 29 июля 2019 на Wayback Machine

Литература[править | править код]

  • О. Оре. Теория графов. — М.: Наука, 1986.