Число предписанное хроматическое: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 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-Jensen]
* Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.

Навигация