4183
правки
Число предписанное хроматическое: различия между версиями
Перейти к навигации
Перейти к поиску
Число предписанное хроматическое (посмотреть исходный код)
Версия от 18:14, 18 мая 2010
, 18 мая 2010нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Число предписанное хроматическое''' (''List chromatic number'') - Идея приписать каждо...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Число предписанное хроматическое''' (''List chromatic number'') - | '''Число предписанное хроматическое''' (''[[List chromatic number]]'') - | ||
Идея приписать каждой вершине <math>v \in V(G)</math> список <math>L(v)</math> с тем, чтобы | Идея приписать каждой [[вершина|вершине]] <math>v \in V(G)</math> список <math>L(v)</math> с тем, чтобы | ||
цвет для вершины <math>v</math> при раскраске вершин графа <math>G</math> избирался из | цвет для вершины <math>v</math> при [[раскраска|раскраске]] вершин [[граф|графа]] <math>G</math> избирался из | ||
списка <math>L(v)</math>, принадлежит В. Визингу (1976) и П. Эрдешу, М. Рабину и Тейлору | списка <math>L(v)</math>, принадлежит В. Визингу (1976) и П. Эрдешу, М. Рабину и Тейлору | ||
(1979). Предписанное хроматическое число <math>\chi_{L}(G)</math> графа <math>G</math> есть | (1979). Предписанное [[хроматическое число]] <math>\chi_{L}(G)</math> графа <math>G</math> есть | ||
наименьшее <math>k</math> такое, что при любом приписывании списков <math>L(v)</math> | наименьшее <math>k</math> такое, что при любом приписывании списков <math>L(v)</math> | ||
мощности <math>|L(v)| \geq k</math> для каждой вершины <math>v \in V(G)</math> возможно | мощности <math>|L(v)| \geq k</math> для каждой вершины <math>v \in V(G)</math> возможно | ||