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

Звездно-хроматическое число (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.]