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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
3-раскраска графа Петерсена

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

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

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

V=\bigcup_i^{} C_i;\ C_i\cap C_j=\varnothing,

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

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

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

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

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

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

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

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

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

Треугольник K_3 t(t-1)(t-2)
Полный граф K_n t(t-1)(t-2) ... (t-(n-1))
Дерево с n вершинами t(t-1)^{n-1}
Цикл C_n (t-1)^n+(-1)^n(t-1)
Граф Петерсена t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)

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

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

|V(G)| = 1 \Rightarrow P(G,t)=t.

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

G_1 \cap G_2 = \emptyset \Rightarrow P((G_1 \cup G_2),t) = P(G_1,t)P(G_2,t).

Также существует рекуррентное соотношение

P(G,t)=P(G-(u,v), t) - P(G/(u,v),t),

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

P(G,t)=P(G+(u,v), t) + P(G \Uparrow (u,v),t),

где u и v — несмежные вершины, а G+(u,v) — граф, получающийся из графа G путем добавления ребра (u,v).

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

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

P(G,t) \ge 0.

Хроматическое число \chi(G) — наименьшее целое положительное t, для которого

P(G,t) > 0.

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

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

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

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

См. также[править | править исходный текст]

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

  1. Birkhoff, G. D. and Lewis, D. C. «Chromatic Polynomials.» Trans. Amer. Math. Soc. 60, 355—451, 1946.

Литература[править | править исходный текст]

  • О. Оре. Теория графов. Перевод с английского И. Н. Врублевской, под редакцией Н. Н. Воробьева. М.: Наука, 1986.