Menu
A node ranking problem is also called an \emph{ordered coloring problem} \([6]\), which labels a graph \( G = (V, E) \) with \( C: V \to \{1, 2, \ldots, k\} \) such that for every path between any two nodes \( u \) and \( v \), with \( C(u) = C(v) \), there is a node \( w \) on the path with \( C(w) > C(u) = C(v) \). The value \( C(v) \) is called the \emph{rank} or color of the node \( v \). Node ranking is the problem of finding the minimum \( k \) such that the maximum rank in \( G \) is \( k \). There are two versions of the node ranking problem: off-line and on-line. In the off-line version, all the vertices and edges are given in advance. In the on-line version, the vertices are given one by one in an arbitrary order (say \( v_1, v_2, \ldots, v_n \)) and only the edges of the induced subgraph \( \langle\{v_1, v_2, \ldots, v_i\}\rangle_G \) are known when the rank of \( v_i \) has to be chosen. This paper establishes the node ranking number of complete \( r \)-partite graphs for the off-line version and gives a tight bound for the on-line version with the algorithms to accomplish them in linear time.