Число Гранди

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

Число Гранди (Grundy number) — раскраской Гранди порядка \,k графа \,G называется \,k-раскраска вершин цветами \{1,2, \ldots, k\} такая, что для любой вершины \,x ее цвет \,c(x) есть минимальное целое число, не использованное на ее соседях. Число Гранди \,\Gamma(G) — наибольшее \,k, для которого \,G имеет раскраску Гранди порядка \,k. Известно, что

\chi(G) \leq \Gamma(G) \leq \Psi(G),

где \,\chi(G) и \,\Psi(G)хроматическое и ахроматическое числа.

Литература

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