- Tytuł:
- On-line ranking number for cycles and paths
- Autorzy:
-
Bruoth, Erik
Horňák, Mirko - Powiązania:
- https://bibliotekanauki.pl/articles/744150.pdf
- Data publikacji:
- 1999
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
ranking number
on-line vertex colouring
cycle
path - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 1999, 19, 2; 175-197
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł