On Node Ranking of Complete $r$-partite Graphs

Abstract

A node ranking problem is also called an $orderedcoloringproblem$ $[6]$, which labels a graph $G=(V,E)$ with $C:V\to \{1,2,\dots ,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 $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,\dots ,v_n$) and only the edges of the induced subgraph $⟨\{v_1,v_2,\dots ,v_i\}{⟩}_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.