A k-ranking of a graph G is a colouring φ:V(G) → 1,...,k such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that for n ≥ 2. Here we show that . The same upper bound is obtained for ,n ≥ 3.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1094,
author = {Erik Bruoth and Mirko Hor\v n\'ak},
title = {On-line ranking number for cycles and paths},
journal = {Discussiones Mathematicae Graph Theory},
volume = {19},
year = {1999},
pages = {175-197},
zbl = {0958.05076},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1094}
}
Erik Bruoth; Mirko Horňák. On-line ranking number for cycles and paths. Discussiones Mathematicae Graph Theory, Tome 19 (1999) pp. 175-197. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1094/
[000] [1] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.
[001] [2] C.E. Leiserson, Area-efficient graph layouts (for VLSI), in: Proc. 21st Annu. IEEE Symp. on Foundations of Computer Science (1980) 270-281.
[002] [3] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Analysis and Appl. 11 (1990) 134-172, doi: 10.1137/0611010. | Zbl 0697.65013
[003] [4] D.C. Llewelyn, C. Tovey and M. Trick, Local optimization on graphs, Discrete Appl. Math. 23 (1989) 157-178, doi: 10.1016/0166-218X(89)90025-5. | Zbl 0675.90085
[004] [5] I. Schiermeyer, Zs. Tuza and M. Voigt, On-line rankings of graphs, submitted.