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

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

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

Литература

  • [Discrete Math.]