Число Гранди

Материал из WEGA
Версия от 16:14, 16 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Число Гранди''' (''Grundy number'') - раскраской Гранди порядка <math>k</math> графа <math>G</m...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Число Гранди (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-Jensen]