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\).

05C38 Paths and cycles
05C15 Coloring of graphs and hypergraphs
Full Text: DOI Link