Geodesic
On-line ranking number for cycles and paths
Discussiones Mathematicae. Graph Theory, Tome 19 (1999) no. 2, pp. 175-197 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 χ*_r(G) 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 χ*_r(Pₙ) 3log₂n for n ≥ 2. Here we show that χ*_r(Pₙ) ≤ 2⎣log₂n⎦+1. The same upper bound is obtained for χ*_r(Cₙ),n ≥ 3.
Keywords: ranking number, on-line vertex colouring, cycle, path 
@article{DMGT_1999_19_2_a5,
     author = {Bruoth, Erik and Hor\v{n}\'ak, Mirko},
     title = {On-line ranking number for cycles and paths},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {175--197},
     year = {1999},
     volume = {19},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a5/}
}
TY  - JOUR
AU  - Bruoth, Erik
AU  - Horňák, Mirko
TI  - On-line ranking number for cycles and paths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 1999
SP  - 175
EP  - 197
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a5/
LA  - en
ID  - DMGT_1999_19_2_a5
ER  - 
%0 Journal Article
%A Bruoth, Erik
%A Horňák, Mirko
%T On-line ranking number for cycles and paths
%J Discussiones Mathematicae. Graph Theory
%D 1999
%P 175-197
%V 19
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a5/
%G en
%F DMGT_1999_19_2_a5
Bruoth, Erik; Horňák, Mirko. On-line ranking number for cycles and paths. Discussiones Mathematicae. Graph Theory, Tome 19 (1999) no. 2, pp. 175-197. http://geodesic.mathdoc.fr/item/DMGT_1999_19_2_a5/

[1] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.

[2] C.E. Leiserson, Area-efficient graph layouts (for VLSI), in: Proc. 21st Annu. IEEE Symp. on Foundations of Computer Science (1980) 270-281.

[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.

[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.

[5] I. Schiermeyer, Zs. Tuza and M. Voigt, On-line rankings of graphs, submitted.