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

Материал из WEGA
Версия от 16:37, 20 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Звездно-хроматическое число''' (''Star-chromatic number'') - Пусть <math>k</math> и <math>d</math> --- ...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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