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

Материал из WikiGrapp
Перейти к:навигация, поиск

Число предписанное хроматическое (List chromatic number) — Идея приписать каждой вершине v \in V(G) список \,L(v) с тем, чтобы цвет для вершины \,v при раскраске вершин графа \,G избирался из списка \,L(v), принадлежит В. Визингу (1976) и П. Эрдешу, М. Рабину и Тейлору (1979). Предписанное хроматическое число \,\chi_{L}(G) графа \,G есть наименьшее \,k такое, что при любом приписывании списков \,L(v) мощности |L(v)| \geq k для каждой вершины v \in V(G) возможно построить вершинную раскраску \,G, выбирая цвета из списков.

Литература

  • Toft B., Jensen T.R. Graph colouring problems. — John Wiley & Sons Inc., 1994.