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

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

Число звездное хроматическое (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\mbox{ имеет }(k,d)-\mbox{раскраску}\}. }[/math]

Литература

[Toft-Jensen]