Упорядоченная раскраска вершин

Материал из WikiGrapp
Версия от 15:06, 9 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Упорядоченная раскраска вершин''' (''Ordered colouring of vertices'') - такая раскраска <mat...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Упорядоченная раскраска вершин (Ordered colouring of vertices) - такая раскраска [math]\displaystyle{ f }[/math] вершин графа [math]\displaystyle{ G }[/math] упорядоченным множеством цветов [math]\displaystyle{ C = \{1,2, \ldots, c\} }[/math], что для любых двух вершин [math]\displaystyle{ x, y }[/math] одинакового цвета, [math]\displaystyle{ f(x) = f(y) }[/math], и любого простого пути [math]\displaystyle{ P(x,y) }[/math], их соединяющего, должна существовать внутренняя вершина [math]\displaystyle{ z }[/math], цвет которой [math]\displaystyle{ f(z) \gt f(x) = f(y) }[/math]. Аналогично определяется упорядоченная раскраска ребер. Упорядоченная раскраска, очевидно, является правильной.

Литература

[Discrete Math.]