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

Упорядоченная раскраска вершин (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.]