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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Число звездное хроматическое''' (''Star chromatic number'') - для <math>(k,d)</math>-раскраски ...)
 
Нет описания правки
Строка 1: Строка 1:
'''Число звездное хроматическое''' (''Star chromatic number'') -  
'''Число звездное хроматическое''' (''[[Star chromatic number]]'') -  
для <math>(k,d)</math>-раскраски графа <math>G</math>, под которой подразумевается такая
для [[(k,d)-Раскраска|<math>(k,d)</math>-раскраски]] [[граф|графа]] <math>G</math>, под которой подразумевается такая
функция <math>\varphi: \, V(G) \rightarrow \{1,2, \ldots, k\}</math>, что <math>d
функция <math>\varphi: \, V(G) \rightarrow \{1,2, \ldots, k\}</math>, что <math>d
\leq |\varphi(u) - \varphi(v)| \leq k-d</math> для каждого ребра <math>(u,v) \in
\leq |\varphi(u) - \varphi(v)| \leq k-d</math> для каждого [[ребро|ребра]] <math>(u,v) \in
E(G)</math>, число
E(G)</math>, число


<math>\chi^{\ast}(G) = \inf\{k/d: \, G\mbox{ имеет }(k,d)-\mbox{раскраску}\}.</math>
<math>\chi^{\ast}(G) = \inf\{k/d: \, G</math> имеет <math>(k,d)</math>-раскраску<math>\}.</math>
==Литература==
==Литература==
[Toft-Jensen]
[Toft-Jensen]

Версия от 11:55, 17 мая 2010

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

Литература

[Toft-Jensen]