Звездно-хроматическое число — различия между версиями

Материал из WikiGrapp
Перейти к:навигация, поиск
(Создана новая страница размером '''Звездно-хроматическое число''' (''Star-chromatic number'') - Пусть <math>k</math> и <math>d</math> --- ...)
 
 
(не показана 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>k \geq 2d</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) — Пусть \,k и \,d — натуральные числа, k \geq 2d. \,(k,d)-раскраской графа \,G=(V,E) называется отображение c: \; V \longrightarrow Z_{k} = \{0,,1,..., k-1\} такое, что для каждого ребра uv \in E |c(u) - c(v)|_{k} \geq d, где \,|x|_{k} = \min\{|x|, k - |x|\}. Это обобщает обычное понятие раскраски. Звездно-хроматическое число \chi^{\star}(G) есть наименьшее \, k/d, при котором граф имеет \,(k,d)-раскраску. Известно, что хроматическое число графа определяется его звездно-хроматическим числом, но обратное неверно.

Литература

  • [Discrete Math.]