Число звездное хроматическое

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

Число звездное хроматическое (Star chromatic number) — для \,(k,d)-раскраски графа \,G, под которой подразумевается такая функция \varphi: \, V(G) \rightarrow \{1,2, \ldots, k\}, что d
\leq |\varphi(u) - \varphi(v)| \leq k-d для каждого ребра (u,v) \in
E(G), число

\chi^{\ast}(G) = \inf\{k/d: \, G имеет \,(k,d)-раскраску\,\}.

Литература

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