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

Упорядоченная раскраска вершин (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)$ . Аналогично определяется упорядоченная раскраска ребер. Упорядоченная раскраска, очевидно, является правильной.