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

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

Хромати́ческое число́ гра́фа G — минимальное число цветов, в которые можно раскрасить[1] вершины графа G так, чтобы концы любого ребра имели разные цвета. Обычно обозначается χ(G).

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

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

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

Связанные определения[править | править код]

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

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

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

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

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

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

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

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

Нахождение хроматического многочлена произвольного графа[править | править код]

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

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

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

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

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

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

Для всех целых положительных

Хроматическое число  — наименьшее целое положительное , для которого

Степень хроматического многочлена равна количеству вершин:

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

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

8 апреля 2018 года, британский математик Обри ди Грей доказал, что [4][5].

Значение для теории графов[править | править код]

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

См. также[править | править код]

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

  1. Раскраска
  2. Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.
  3. http://www.allmath.ru/highermath/algebra/graph/graph5.htm
  4. de Grey, Aubrey D.N.J (2018-04-08), The chromatic number of the plane is at least 5 
  5. Владимир Королёв. Математикам не хватило четырех цветов для раскраски плоскости. nplus1.ru. Проверено 11 апреля 2018.

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

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