On-line ranking number for cycles and paths

Erik Bruoth; Mirko Horňák

Discussiones Mathematicae Graph Theory (1999)

  • Volume: 19, Issue: 2, page 175-197
  • ISSN: 2083-5892

Abstract

top
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 ( P ₙ ) < 3 l o g ₂ n for n ≥ 2. Here we show that χ * r ( P ₙ ) ≤ 2 ⎣ l o g ₂ n ⎦ + 1 . The same upper bound is obtained for χ * r ( C ₙ ) ,n ≥ 3.

How to cite

top

Erik Bruoth, and Mirko Horňák. "On-line ranking number for cycles and paths." Discussiones Mathematicae Graph Theory 19.2 (1999): 175-197. <http://eudml.org/doc/270736>.

@article{ErikBruoth1999,
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(Pₙ) < 3log₂n$ for n ≥ 2. Here we show that $χ*_r(Pₙ) ≤ 2⎣log₂n⎦+1$. The same upper bound is obtained for $χ*_r(Cₙ)$,n ≥ 3.},
author = {Erik Bruoth, Mirko Horňák},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {ranking number; on-line vertex colouring; cycle; path; colouring},
language = {eng},
number = {2},
pages = {175-197},
title = {On-line ranking number for cycles and paths},
url = {http://eudml.org/doc/270736},
volume = {19},
year = {1999},
}

TY - JOUR
AU - Erik Bruoth
AU - Mirko Horňák
TI - On-line ranking number for cycles and paths
JO - Discussiones Mathematicae Graph Theory
PY - 1999
VL - 19
IS - 2
SP - 175
EP - 197
AB - 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(Pₙ) < 3log₂n$ for n ≥ 2. Here we show that $χ*_r(Pₙ) ≤ 2⎣log₂n⎦+1$. The same upper bound is obtained for $χ*_r(Cₙ)$,n ≥ 3.
LA - eng
KW - ranking number; on-line vertex colouring; cycle; path; colouring
UR - http://eudml.org/doc/270736
ER -

References

top
  1. [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. [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. [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. Zbl0697.65013
  4. [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. Zbl0675.90085
  5. [5] I. Schiermeyer, Zs. Tuza and M. Voigt, On-line rankings of graphs, submitted. 

NotesEmbed ?

top

You must be logged in to post comments.