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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.