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

A k-ranking of a graph G   is a mapping ϕ:V(G)→{1,…,k}ϕ:V(G)→{1,…,k} such that any path with endvertices x and y   satisfying x≠yx≠y and ϕ(x)=ϕ(y)ϕ(x)=ϕ(y) contains a vertex z   with ϕ(z)>ϕ(x)ϕ(z)>ϕ(x). The ranking number χr(G)χ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.