19-10-2023
Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).
Содержание |
Хроматическое число графа — минимальное число , такое что множество вершин графа можно разбить на непересекающихся классов :
таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса.
Хроматический класс графа G — минимальное число цветов, в которые можно раскрасить ребра графа G так, чтобы смежные ребра имели разные цвета. Обозначается χ'(G). Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырех красок. Реберная раскраска определяет 1-факторизацию графа.
Если рассмотреть количество различных раскрасок помеченного графа как функцию от доступного числа цветов t, то оказывается, что эта функция всегда будет полиномом от t. Этот факт был обнаружен Биркгофом и Льюисом [1] при попытке доказать гипотезу четырех красок.
Треугольник | |
Полный граф | |
Дерево с вершинами | |
Цикл | |
Граф Петерсена |
Для графа-вершины хроматический многочлен равен
Хроматический многочлен графа равен произведению хроматических многочленов его компонент
Также существует рекуррентное соотношение
где и — смежные вершины, — граф, получающийся из графа путем удаления ребра а — граф, получающийся из графа путем стягивания ребра в точку.
Можно использовать эквивалентную формулу
где и — несмежные вершины, а — граф, получающийся из графа путем добавления ребра
Для всех целых положительных
Хроматическое число — наименьшее целое положительное , для которого
Также хроматическое число можно рассматривать для других объектов, например, для метрических пространств. Так, хроматическим числом плоскости называется минимальное число χ такое, что существует раскраска всех точек плоскости в один из χ цветов и при этом никакие две точки одного цвета не находятся на расстоянии 1 друг от друга (плоскость не содержит монохроматических отрезков длины 1). Аналогично для любой размерности пространства. Элементарно доказывается, что для плоскости , однако больше до сих пор неизвестно - эта проблема носит название Хадвигера-Нельсона (англ.).
Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырёх красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырёх красок, гипотеза Хадвигера.
Раскраска графа.