K-Ranking

[math]\displaystyle{ k }[/math]-Ranking --- [math]\displaystyle{ k }[/math]-ранжирование.

Given an undirected graph [math]\displaystyle{ G }[/math], a (vertex) [math]\displaystyle{ k }[/math]-ranking of [math]\displaystyle{ G }[/math] is a mapping (coloring) [math]\displaystyle{ f: \; V(G) \rightarrow \{1, 2, \ldots, k\} }[/math] such that every path connecting two vertices [math]\displaystyle{ u, v }[/math] of the same rank [math]\displaystyle{ f(u) = f(v) }[/math] contains a vertex [math]\displaystyle{ w }[/math] with a higher rank, [math]\displaystyle{ f(w) \gt f(u) }[/math]. The ranking number [math]\displaystyle{ \chi_{r}(G) }[/math] is the minimum integer [math]\displaystyle{ k }[/math] for which there exists a [math]\displaystyle{ k }[/math]-ranking.

It is well known and easy to see that, for the path [math]\displaystyle{ P_{L} }[/math] of length [math]\displaystyle{ L-1 }[/math] on [math]\displaystyle{ L }[/math] vertices, we have

[math]\displaystyle{ \chi_{r}(P_{L}) = \lfloor \log L\rfloor + 1 }[/math]

and that the longest [math]\displaystyle{ k }[/math]-rankable path [math]\displaystyle{ P_{2^{k}-1} = x_{1}x_{2}\ldots x_{2^{k}-1} }[/math] admits the unique optimal ranking [math]\displaystyle{ f }[/math] with

[math]\displaystyle{ f(x_{i}) = \max\{j: \; 2^{j}|i\} + 1 }[/math]

for all [math]\displaystyle{ 1 \leq i \lt 2^{k} }[/math].

Analogously, [math]\displaystyle{ k }[/math]-ranking for directed graphs is defined.