Edge t-ranking

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

Let [math]\displaystyle{ G = (V,E) }[/math] be a graph and [math]\displaystyle{ t }[/math] be a positive integer. An edge [math]\displaystyle{ t }[/math]-ranking is an edge coloring [math]\displaystyle{ c': \; E \rightarrow \{1, \ldots, t\} }[/math] such that for every pair of edges [math]\displaystyle{ e }[/math] and [math]\displaystyle{ f }[/math] with [math]\displaystyle{ c'(e) = c'(f) }[/math], there is an edge [math]\displaystyle{ g }[/math] on every path between [math]\displaystyle{ e }[/math] and [math]\displaystyle{ f }[/math] with [math]\displaystyle{ c'(g) \gt c'(e) }[/math]. The edge ranking number, [math]\displaystyle{ \chi'_{r}(G) }[/math], is the smallest value of [math]\displaystyle{ t }[/math] such that [math]\displaystyle{ G }[/math] has an edge [math]\displaystyle{ t }[/math]-ranking.

See also

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