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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

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