A vertex ranking of a graph  G  is an assignment of#N#positive integers (colors) to the vertices of  G  such that#N#each path connecting two vertices of the same color contains a vertex#N#of a higher color. Our main goal is to find a vertex ranking using as#N#few colors as possible. Considering on-line algorithms for vertex#N#ranking of split graphs, we prove that the worst case ratio of the#N#number of colors used by any on-line ranking algorithm and the number#N#of colors used in an optimal off-line solution may be arbitrarily#N#large. This negative result motivates us to investigate semi on-line#N#algorithms, where a split graph is presented on-line but its clique#N#number is given in advance. We prove that there does not exist a#N# (2-ɛ) -competitive semi on-line algorithm of this#N#type.  Finally, a  2 -competitive semi on-line algorithm is#N#given.
['Piotr Borowiecki', 'Dariusz Dereniowski']
On-line ranking of split graphs