DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 19(2) (1999) 175-197
DOI: 10.7151/dmgt.1094

ON-LINE RANKING NUMBER FOR CYCLES AND PATHS

Erik Bruoth and Mirko Hornák

Department of Geometry and Algebra
P.J. Safárik University, Jesenná 5
041 54 Košice, Slovakia

e-mail: ebruoth@duro.upjs.sk
e-mail: hornak@turing.upjs.sk

Abstract

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 χ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. Schiermeyer, Tuza and Voigt proved that χr*(Pn) < 3log2n for n ≥ 2. Here we show that χr*(Pn) ≤ 2⎣log2n⎦+1. The same upper bound is obtained for χr*(Cn),n ≥ 3.

Keywords: ranking number, on-line vertex colouring, cycle, path.

1991 Mathematics Subject Classification: 05C15.

References

[1] M. Katchalski, W. McCuaig and S. Seager, Ordered colourings, Discrete Math. 142 (1995) 141-154, doi: 10.1016/0012-365X(93)E0216-Q.
[2] C.E. Leiserson, Area-efficient graph layouts (for VLSI), in: Proc. 21st Annu. IEEE Symp. on Foundations of Computer Science (1980) 270-281.
[3] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM J. Matrix Analysis and Appl. 11 (1990) 134-172, doi: 10.1137/0611010.
[4] D.C. Llewelyn, C. Tovey and M. Trick, Local optimization on graphs, Discrete Appl. Math. 23 (1989) 157-178, doi: 10.1016/0166-218X(89)90025-5.
[5] I. Schiermeyer, Zs. Tuza and M. Voigt, On-line rankings of graphs, submitted.

Received 22 February 1999
Revised 29 October 1999