zbMATH — the first resource for mathematics

On-line ranking number for cycles and paths. (English) Zbl 0958.05076
Summary: A $$k$$-ranking of a graph $$G$$ is a colouring $$\varphi: V(G)\to \{1,\dots, k\}$$ such that any path in $$G$$ with endvertices $$x$$, $$y$$ fulfilling $$\varphi(x)= \varphi(y)$$ contains an internal vertex $$z$$ with $$\varphi(z)> \varphi(x)$$. On-line ranking number $$\chi^*_r(G)$$ 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. I. Schiermeyer, Zs. Tuza and M. Voigt [Discrete Math. 212, No. 1-2, 141-147 (2000; Zbl 0946.05039)] proved that $$\chi^*_r(P_n)< 3\log_2n$$ for $$n\geq 2$$. Here we show that $$\chi^*_r(P_n)\leq 2\lfloor\log_2 n\rfloor+ 1$$. The same upper bound is obtained for $$\chi^*_r(C_n)$$, $$n\geq 3$$.

MSC:
 05C38 Paths and cycles 05C15 Coloring of graphs and hypergraphs
Keywords:
colouring; path; ranking number
Full Text: