Число предписанное хроматическое

Число предписанное хроматическое (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.