A lower bound for on-line ranking number of a path

AbstractA k-ranking of a graph G is a mapping ϕ:V(G)→{1,…,k} such that any path with endvertices x and y satisfying x≠y and ϕ(x)=ϕ(y) contains a vertex z with ϕ(z)>ϕ(x). The ranking number χr(G) of G is the minimum k admitting a k-ranking of G. The on-line ranking number χ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 ⌊log2n⌋+1=χr(Pn)⩽χr*(Pn)⩽2⌊log2n⌋+1. In this paper it is proved that χr*(Pn)>1.619log2n-1