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 chi(r)(G) is the smallest value of t such that G has a vertex t-ranking. A chi(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. (C) 2002 Elsevier Science B.V. All rights reserved.
vertex ranking starlike graphs algorithms split graphs