| Title:
|
A note on on-line ranking number of graphs (English) |
| Author:
|
Semanišin, G. |
| Author:
|
Soták, R. |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
56 |
| Issue:
|
2 |
| Year:
|
2006 |
| Pages:
|
591-599 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
on-line ranking number |
| Keyword:
|
complete $n$-partite graph |
| Keyword:
|
hereditary and additive properties of graphs |
| MSC:
|
05C15 |
| MSC:
|
05C78 |
| MSC:
|
05C85 |
| idZBL:
|
Zbl 1164.05360 |
| idMR:
|
MR2291759 |
| . |
| Date available:
|
2009-09-24T11:35:52Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128089 |
| . |
| Reference:
|
[1] B. Bollobás: Extremal Graph Theory.Academic Press, London, 1978. MR 0506522 |
| Reference:
|
[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. MR 1633268, 10.7151/dmgt.1037 |
| Reference:
|
[3] J. I. Brown, D. G. Corneil: On generalized graph colourings.J. Graph Theory 11 (1987), 86–99. MR 0876208, 10.1002/jgt.3190110113 |
| Reference:
|
[4] E. Bruoth, M. Horňák: On-line ranking number for cycles and paths.Discuss. Math. Graph Theory 19 (1999), 175–197. MR 1768300, 10.7151/dmgt.1094 |
| Reference:
|
[5] E. Bruoth, M. Horňák: A lower bound for on-line ranking number of a path.Discrete Math (to appear). MR 2311106 |
| Reference:
|
[6] I. Schiermayer, Zs. Tuza, and M. Voigt: On-line ranking of graphs.Discrete Math. 212 (2000), 141–147. MR 1748681, 10.1016/S0012-365X(99)00215-0 |
| Reference:
|
[7] M. Weaver, D. B. West: Relaxed chromatic numbers of graphs.Graphs Comb. 10 (1994), 75–93. MR 1273014, 10.1007/BF01202473 |
| . |
