On-line rankings of graphs
Please always quote using this URN: urn:nbn:de:0297-zib-3011
- 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.
Download full text files
Additional Services
| Author: | Ingo Schiermeyer, Zsolt Tuza, Margit Voigt |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1997/07/10 |
| Series (Serial Number): | ZIB-Report (SC-97-32) |
| ZIB-Reportnumber: | SC-97-32 |
| Published in: | Appeared in: Discrete Mathematics, 212 (2000), 141-147 |
