Звездно-хроматическое число: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Звездно-хроматическое число''' (''Star-chromatic number'') - Пусть <math>k</math> и <math>d</math> --- ...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Звездно-хроматическое число''' (''Star-chromatic number'') | '''Звездно-хроматическое число''' (''[[Star-chromatic number]]'') — Пусть <math>\,k</math> и <math>\,d</math> — натуральные числа, <math>k \geq 2d</math>. [[(k,d)-Раскраска|<math>\,(k,d)</math>-'''раскраской''']] [[граф|графа]] <math>\,G=(V,E)</math> называется отображение <math>c: \; V \longrightarrow Z_{k} = \{0,,1,..., k-1\}</math> такое, что для каждого [[ребро|ребра]] <math>uv \in E</math> <math>|c(u) - c(v)|_{k} \geq d</math>, где <math>\,|x|_{k} = \min\{|x|, k - |x|\}</math>. Это обобщает обычное понятие [[раскраска|раскраски]]. '''Звездно-хроматическое число''' | ||
Пусть <math>k</math> и <math>d</math> | <math>\chi^{\star}(G)</math> есть наименьшее <math>\, k/d</math>, при котором граф имеет <math>\,(k,d)</math>-раскраску. Известно, что [[хроматическое число]] графа определяется его звездно-хроматическим числом, но обратное неверно. | ||
<math>(k,d)</math>-'''раскраской''' | |||
графа <math>G=(V,E)</math> называется отображение <math>c: \; V \longrightarrow Z_{k} | |||
= \{0,,1,..., k-1\}</math> такое, что для каждого ребра <math>uv \in E</math> <math>|c(u) - | |||
c(v)|_{k} \geq d</math>, где <math>|x|_{k} = \min\{|x|, k - |x|\}</math>. Это обобщает | |||
обычное понятие раскраски. ''' | |||
<math>\chi^{\star}(G)</math> есть наименьшее <math>k/d</math>, при котором граф имеет | |||
<math>(k,d)</math>-раскраску. Известно, что хроматическое число графа | |||
определяется его звездно-хроматическим числом, но обратное неверно. | |||
==Литература== | ==Литература== | ||
[Discrete Math.] | * [Discrete Math.] | ||
Текущая версия от 15:59, 18 февраля 2011
Звездно-хроматическое число (Star-chromatic number) — Пусть [math]\displaystyle{ \,k }[/math] и [math]\displaystyle{ \,d }[/math] — натуральные числа, [math]\displaystyle{ k \geq 2d }[/math]. [math]\displaystyle{ \,(k,d) }[/math]-раскраской графа [math]\displaystyle{ \,G=(V,E) }[/math] называется отображение [math]\displaystyle{ c: \; V \longrightarrow Z_{k} = \{0,,1,..., k-1\} }[/math] такое, что для каждого ребра [math]\displaystyle{ uv \in E }[/math] [math]\displaystyle{ |c(u) - c(v)|_{k} \geq d }[/math], где [math]\displaystyle{ \,|x|_{k} = \min\{|x|, k - |x|\} }[/math]. Это обобщает обычное понятие раскраски. Звездно-хроматическое число [math]\displaystyle{ \chi^{\star}(G) }[/math] есть наименьшее [math]\displaystyle{ \, k/d }[/math], при котором граф имеет [math]\displaystyle{ \,(k,d) }[/math]-раскраску. Известно, что хроматическое число графа определяется его звездно-хроматическим числом, но обратное неверно.
Литература
- [Discrete Math.]