On-line ranking number for cycles and paths

A k-ranking of a graph G is a colouring φ:V(G) → {1,...,k} such that any path in G with endvertices x,y fulfilling φ(x) = φ(y) contains an internal vertex z with φ(z) > φ(x). On-line ranking number ${\displaystyle \chi {\cdot }_r\left(G\right)}$ of a graph G is a minimum k such that G has a k-ranking constructed step by step if vertices of G are coming and coloured one by one in an arbitrary order; when colouring a vertex, only edges between already present vertices are known. Schiermeyer, Tuza and Voigt proved that ${\displaystyle \chi {\cdot }_r(Pₙ)<3\log ₂n}$ for n ≥ 2. Here we show that ${\displaystyle \chi {\cdot }_r(Pₙ)\le 2⎣\log ₂n⎦+1}$. The same upper bound is obtained for ${\displaystyle \chi {\cdot }_r(Cₙ)}$,n ≥ 3.