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

Звездно-хроматическое число (Star-chromatic number) - Пусть [math]\displaystyle{ k }[/math] и [math]\displaystyle{ d }[/math] --- натуральные числа, [math]\displaystyle{ k \geq 2d }[/math]. [math]\displaystyle{ (k,d) }[/math]-раскраской графа [math]\displaystyle{ G=(V,E) }[/math] называется отображение [math]\displaystyle{ c: \; V \longrightarrow Z_{k} = \{0,,1,..., k-1\} }[/math] такое, что для каждого ребра [math]\displaystyle{ uv \in E }[/math] [math]\displaystyle{ |c(u) - c(v)|_{k} \geq d }[/math], где [math]\displaystyle{ |x|_{k} = \min\{|x|, k - |x|\} }[/math]. Это обобщает обычное понятие раскраски. З.-х.ч. [math]\displaystyle{ \chi^{\star}(G) }[/math] есть наименьшее [math]\displaystyle{ k/d }[/math], при котором граф имеет [math]\displaystyle{ (k,d) }[/math]-раскраску. Известно, что хроматическое число графа определяется его звездно-хроматическим числом, но обратное неверно.

Литература

[Discrete Math.]