4624
правки
Число звездное хроматическое: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Число звездное хроматическое''' (''Star chromatic number'') - для <math>(k,d)</math>-раскраски ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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 | <math>\chi^{\ast}(G) = \inf\{k/d: \, G</math> имеет <math>(k,d)</math>-раскраску<math>\}.</math> | ||
==Литература== | ==Литература== | ||
[Toft-Jensen] | [Toft-Jensen] | ||