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

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

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

Литература

[Discrete Math.]