Число звездное хроматическое: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Число звездное хроматическое''' (''Star chromatic number'') - для <math>(k,d)</math>-раскраски ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Число звездное хроматическое''' (''Star chromatic number'') - | '''Число звездное хроматическое''' (''[[Star-chromatic number|Star chromatic number]]'') — для [[(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> | \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 B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994. | |||
Текущая версия от 13:47, 6 октября 2011
Число звездное хроматическое (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 B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.