Число Гранди: различия между версиями

'''Число Гранди''' (''[[Grundy number]]'') — ''[[раскраска|раскраской]] Гранди порядка <math>\,k</math> графа <math>\,G</math>'' называется [[k-Раскраска|<math>\,k</math>-раскраска]]

[[вершина|вершин]] цветами <math>\{1,2, \ldots, k\}</math> такая, что для любой вершины <math>\,x</math> ее цвет <math>\,c(x)</math> есть минимальное целое число, не использованное на ее

соседях. '''Число Гранди''' <math>\,\Gamma(G)</math> — наибольшее <math>\,k</math>, для которого <math>\,G</math> имеет раскраску Гранди порядка <math>\,k.</math> Известно, что

:::::<math>\chi(G) \leq \Gamma(G) \leq \Psi(G),</math>

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

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