On vertex ranking of a starlike graph

A vertex coloring c:V → {1,2,...,t} of a graph G = (V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ(r)(G) is the smallest value of t such that G has a vertex t-ranking. A χ(r)(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V| + |E|) time algorithm for finding an optimal vertex ranking of a starlike graph G = (V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.