Geodesic
A note on on-line ranking number of graphs
Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 591-599
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A $k$-ranking of a graph $G=(V,E)$ is a mapping $\varphi \:V \rightarrow \lbrace 1,2,\dots ,k\rbrace $ such that each path with endvertices of the same colour $c$ contains an internal vertex with colour greater than $c$. The ranking number of a graph $G$ is the smallest positive integer $k$ admitting a $k$-ranking of $G$. In the on-line version of the problem, the vertices $v_1,v_2,\dots ,v_n$ of $G$ arrive one by one in an arbitrary order, and only the edges of the induced graph $G[\lbrace v_1,v_2,\dots ,v_i\rbrace ]$ are known when the colour for the vertex $v_i$ has to be chosen. The on-line ranking number of a graph $G$ is the smallest positive integer $k$ such that there exists an algorithm that produces a $k$-ranking of $G$ for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete $n$-partite graphs. The question of additivity and heredity is discussed as well.
A $k$-ranking of a graph $G=(V,E)$ is a mapping $\varphi \:V \rightarrow \lbrace 1,2,\dots ,k\rbrace $ such that each path with endvertices of the same colour $c$ contains an internal vertex with colour greater than $c$. The ranking number of a graph $G$ is the smallest positive integer $k$ admitting a $k$-ranking of $G$. In the on-line version of the problem, the vertices $v_1,v_2,\dots ,v_n$ of $G$ arrive one by one in an arbitrary order, and only the edges of the induced graph $G[\lbrace v_1,v_2,\dots ,v_i\rbrace ]$ are known when the colour for the vertex $v_i$ has to be chosen. The on-line ranking number of a graph $G$ is the smallest positive integer $k$ such that there exists an algorithm that produces a $k$-ranking of $G$ for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete $n$-partite graphs. The question of additivity and heredity is discussed as well.
Classification : 05C15, 05C78, 05C85
Keywords: on-line ranking number; complete $n$-partite graph; hereditary and additive properties of graphs 
@article{CMJ_2006_56_2_a23,
     author = {Semani\v{s}in, G. and Sot\'ak, R.},
     title = {A note on on-line ranking number of graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {591--599},
     year = {2006},
     volume = {56},
     number = {2},
     mrnumber = {2291759},
     zbl = {1164.05360},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a23/}
}
TY  - JOUR
AU  - Semanišin, G.
AU  - Soták, R.
TI  - A note on on-line ranking number of graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2006
SP  - 591
EP  - 599
VL  - 56
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a23/
LA  - en
ID  - CMJ_2006_56_2_a23
ER  - 
%0 Journal Article
%A Semanišin, G.
%A Soták, R.
%T A note on on-line ranking number of graphs
%J Czechoslovak Mathematical Journal
%D 2006
%P 591-599
%V 56
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a23/
%G en
%F CMJ_2006_56_2_a23
Semanišin, G.; Soták, R. A note on on-line ranking number of graphs. Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 591-599. http://geodesic.mathdoc.fr/item/CMJ_2006_56_2_a23/

[1] B.  Bollobás: Extremal Graph Theory. Academic Press, London, 1978. | MR

[2] M.  Borowiecki, I.  Broere, M.  Frick, P.  Mihók, and G.  Semanišin: Survey of hereditary properties of graphs. Discuss. Math. Graph Theory 17 (1997), 5–50. | DOI | MR

[3] J. I.  Brown, D. G.  Corneil: On generalized graph colourings. J.  Graph Theory 11 (1987), 86–99. | DOI | MR

[4] E.  Bruoth, M.  Horňák: On-line ranking number for cycles and paths. Discuss. Math. Graph Theory 19 (1999), 175–197. | DOI | MR

[5] E.  Bruoth, M.  Horňák: A lower bound for on-line ranking number of a path. Discrete Math (to appear). | MR

[6] I.  Schiermayer, Zs. Tuza, and M.  Voigt: On-line ranking of graphs. Discrete Math. 212 (2000), 141–147. | DOI | MR

[7] M. Weaver, D. B.  West: Relaxed chromatic numbers of graphs. Graphs Comb. 10 (1994), 75–93. | DOI | MR