Число Гранди

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

[math]\displaystyle{ \chi(G) \leq \Gamma(G) \leq \Psi(G), }[/math]

где [math]\displaystyle{ \,\chi(G) }[/math] и [math]\displaystyle{ \,\Psi(G) }[/math] — хроматическое и ахроматическое числа.

Литература

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