TY - GEN A1 - Schiermeyer, Ingo A1 - Tuza, Zsolt A1 - Voigt, Margit T1 - On-line rankings of graphs N2 - A (vertex) $k$-ranking of a graph $G=(V,E)$ is a mapping $ p:V\to \{1,\dots,k\}$ such that each path with endvertices of the same color $i$ contains an internal vertex of color $\ge i+1$. In the on-line coloring algorithms, the vertices $v_1,\dots,v_n$ arrive one by one in an unrestricted order, and only the edges inside the set $\{v_1,\dots,v_i\}$ are known when the color of $v_i$ has to be chosen. We characterize those graphs for which a 3-ranking can be found on-line. We also prove that the greedy (First-Fit) on-line algorithm, assigning the smallest feasible color to the next vertex at each step, generates a $(3\log_2 n)$-ranking for the path with $n \geq 2$ vertices, independently of the order in which the vertices are received. T3 - ZIB-Report - SC-97-32 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3011 ER -