@misc{SchiermeyerTuzaVoigt, author = {Schiermeyer, Ingo and Tuza, Zsolt and Voigt, Margit}, title = {On-line rankings of graphs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3011}, number = {SC-97-32}, abstract = {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.}, language = {en} }