Число подхроматическое

Материал из WEGA
Версия от 11:55, 7 октября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Число подхроматическое (Subchromatic number) — (обозначение [math]\displaystyle{ \,\chi_{S}(G) }[/math]) наименьшее целое [math]\displaystyle{ \,k }[/math] такое, что вершины графа могут быть разбиты на [math]\displaystyle{ \,k }[/math] множеств [math]\displaystyle{ V_{1}, \, V_{2}, \, \ldots, \, V_{k} }[/math] такие, что каждый индуцированный подграф [math]\displaystyle{ \,G[V_{i}] }[/math] есть непересекающееся объединение полных графов. Число подхроматическое было введено в 1985 г. Мынхардтом и Броере.

Литература

  • Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.