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

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

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

Литература

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