PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1999 | 19 | 2 | 175-197
Tytuł artykułu

On-line ranking number for cycles and paths

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
Wydawca
Rocznik
Tom
19
Numer
2
Strony
175-197
Opis fizyczny
Daty
wydano
1999
Twórcy
autor
  • Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia
  • Department of Geometry and Algebra, P.J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1094
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.