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

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