Vertex t-ranking

Vertex [math]\displaystyle{ t }[/math]-ranking --- вершинное [math]\displaystyle{ t }[/math]-ранжирование.

Let [math]\displaystyle{ G = (V,E) }[/math] be a graph and let [math]\displaystyle{ t }[/math] be a positive integer. A vertex [math]\displaystyle{ t }[/math]-ranking, called ranking for short if there is no ambiguity, is a coloring [math]\displaystyle{ c: \; V \rightarrow \{1, \ldots, t\} }[/math] such that, for every pair of vertices [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] with [math]\displaystyle{ c(x) = c(y) }[/math] and for every path between [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], there is a vertex [math]\displaystyle{ z }[/math] on this path with [math]\displaystyle{ c(z) \gt c(x) }[/math]. The vertex ranking number of [math]\displaystyle{ G }[/math], [math]\displaystyle{ \chi_{r}(G) }[/math], is the smallest [math]\displaystyle{ t }[/math] for which the graph [math]\displaystyle{ G }[/math] admits a [math]\displaystyle{ t }[/math]-ranking.

See also

• Edge [math]\displaystyle{ t }[/math]-ranking.