Число предписанное хроматическое: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Число предписанное хроматическое''' (''List chromatic number'') - Идея приписать каждо...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Число предписанное хроматическое''' (''List chromatic number'') | '''Число предписанное хроматическое''' (''[[List chromatic number]]'') — Идея приписать каждой [[вершина|вершине]] <math>v \in V(G)</math> список <math>\,L(v)</math> с тем, чтобы цвет для вершины <math>\,v</math> при [[раскраска|раскраске]] вершин [[граф|графа]] <math>\,G</math> избирался из списка <math>\,L(v)</math>, принадлежит В. Визингу (1976) и П. Эрдешу, М. Рабину и Тейлору (1979). Предписанное [[хроматическое число]] <math>\,\chi_{L}(G)</math> графа <math>\,G</math> есть наименьшее <math>\,k</math> такое, что при любом приписывании списков <math>\,L(v)</math> мощности <math>|L(v)| \geq k</math> для каждой вершины <math>v \in V(G)</math> возможно | ||
Идея приписать каждой вершине <math>v \in V(G)</math> список <math>L(v)</math> с тем, чтобы | построить вершинную раскраску <math>\,G</math>, выбирая цвета из списков. | ||
цвет для вершины <math>v</math> при раскраске вершин графа <math>G</math> избирался из | |||
списка <math>L(v)</math>, принадлежит В. Визингу (1976) и П. Эрдешу, М. Рабину и Тейлору | |||
(1979). Предписанное хроматическое число <math>\chi_{L}(G)</math> графа <math>G</math> есть | |||
наименьшее <math>k</math> такое, что при любом приписывании списков <math>L(v)</math> | |||
мощности <math>|L(v)| \geq k</math> для каждой вершины <math>v \in V(G)</math> возможно | |||
построить вершинную раскраску <math>G</math>, выбирая цвета из списков. | |||
==Литература== | ==Литература== | ||
* Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994. | |||
Текущая версия от 12:09, 7 октября 2011
Число предписанное хроматическое (List chromatic number) — Идея приписать каждой вершине [math]\displaystyle{ v \in V(G) }[/math] список [math]\displaystyle{ \,L(v) }[/math] с тем, чтобы цвет для вершины [math]\displaystyle{ \,v }[/math] при раскраске вершин графа [math]\displaystyle{ \,G }[/math] избирался из списка [math]\displaystyle{ \,L(v) }[/math], принадлежит В. Визингу (1976) и П. Эрдешу, М. Рабину и Тейлору (1979). Предписанное хроматическое число [math]\displaystyle{ \,\chi_{L}(G) }[/math] графа [math]\displaystyle{ \,G }[/math] есть наименьшее [math]\displaystyle{ \,k }[/math] такое, что при любом приписывании списков [math]\displaystyle{ \,L(v) }[/math] мощности [math]\displaystyle{ |L(v)| \geq k }[/math] для каждой вершины [math]\displaystyle{ v \in V(G) }[/math] возможно построить вершинную раскраску [math]\displaystyle{ \,G }[/math], выбирая цвета из списков.
Литература
- Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.