zbMATH — the first resource for mathematics

A lower bound for on-line ranking number of a path. (English) Zbl 1115.05047
Summary: A \(k\)-ranking of a graph \(G\) is a mapping \(\varphi:V(G)\to\{1, \dots,k\}\) such that any path with endvertices \(x\) and \(y\) satisfying \(x\neq y\) and \(\varphi(x)= \varphi(y)\) contains a vertex \(z\) with \(\varphi(z)>\varphi(x)\). The ranking number \(\chi_r(G)\) of \(G\) is the minimum \(k\) admitting a \(k\)-ranking of \(G\). The on-line ranking number \(\chi^*_r(G)\) of \(G\) is the corresponding on-line invariant; in that case vertices of \(G\) are coming one by one so that a partial ranking has to be chosen by considering only the structure of the subgraph of \(G\) induced by the present vertices. It is known that \(\lfloor\log_2n\rfloor+1 =\chi_r(P_n)\leq\chi_r^*(P_n)\leq 2\lfloor\log_2n\rfloor+1\). In this paper it is proved that \(\chi^*_r(P_n)>1.619\log_2n-1\).

05C38 Paths and cycles
Full Text: DOI
[1] Bodlaender, H.L.; Deogun, J.S.; Jansen, K.; Kloks, T.; Kratsch, D.; Müller, H.; Tuza, Zs., Rankings of graphs, SIAM J. discrete math., 11, 168-181, (1998) · Zbl 0907.68137
[2] Bruoth, E.; Horňák, M., On-line ranking number for cycles and paths, Discuss. math. graph theory, 19, 175-197, (1999) · Zbl 0958.05076
[3] Deogun, J.S.; Kloks, T.; Kratsch, D.; Müller, H., On the vertex ranking problem for trapezoid, Circular-arc and other graphs, discrete appl. math., 98, 39-63, (1999) · Zbl 0937.68093
[4] Ghoshal, J.; Laskar, R.; Pillone, D., Minimal rankings, Networks, 28, 45-53, (1996) · Zbl 0863.05071
[5] Ghoshal, J.; Laskar, R.; Pillone, D., Further results on minimal rankings, Ars combin., 52, 181-198, (1999) · Zbl 0977.05048
[6] Iyer, A.V.; Ratliff, H.D.; Vijayan, G., Optimal node ranking of trees, Inform. process. lett., 28, 225-229, (1988) · Zbl 0661.68063
[7] Katchalski, M.; McCuaig, W.; Seager, S., Ordered colourings, Discrete math., 142, 141-154, (1995) · Zbl 0842.05032
[8] Kratochvíl, J.; Tuza, Zs., Rankings of directed graphs, SIAM J. discrete math., 12, 374-384, (1999) · Zbl 0932.05032
[9] Lam, T.W.; Yue, F.L., Edge ranking of graphs is hard, Discrete appl. math., 85, 71-86, (1998) · Zbl 0902.68088
[10] Llewellyn, D.C.; Tovey, C.; Trick, M., Local optimization on graphs, Discrete appl. math., 23, 157-178, (1989) · Zbl 0675.90085
[11] Schiermeyer, I.; Tuza, Zs.; Voigt, M., On-line rankings of graphs, Discrete math., 212, 141-147, (2000) · Zbl 0946.05039
[12] G. Semanišin, R. Soták, A note on on-line ranking of graphs, Czechoslovak Math. J. 56(131) (2006) 591-599.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.