A note on on-line ranking number of graphs

Semanišin, Gabriel, and Soták, Roman. "A note on on-line ranking number of graphs." Czechoslovak Mathematical Journal 56.2 (2006): 591-599. <http://eudml.org/doc/31051>.

@article{Semanišin2006,
abstract = {A $k$-ranking of a graph $G=(V,E)$ is a mapping $\varphi \:V \rightarrow \lbrace 1,2,\dots ,k\rbrace $ such that each path with endvertices of the same colour $c$ contains an internal vertex with colour greater than $c$. The ranking number of a graph $G$ is the smallest positive integer $k$ admitting a $k$-ranking of $G$. In the on-line version of the problem, the vertices $v_1,v_2,\dots ,v_n$ of $G$ arrive one by one in an arbitrary order, and only the edges of the induced graph $G[\lbrace v_1,v_2,\dots ,v_i\rbrace ]$ are known when the colour for the vertex $v_i$ has to be chosen. The on-line ranking number of a graph $G$ is the smallest positive integer $k$ such that there exists an algorithm that produces a $k$-ranking of $G$ for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete $n$-partite graphs. The question of additivity and heredity is discussed as well.},
author = {Semanišin, Gabriel, Soták, Roman},
journal = {Czechoslovak Mathematical Journal},
keywords = {on-line ranking number; complete $n$-partite graph; hereditary and additive properties of graphs; on-line ranking number; complete -partite graph; hereditary and additive properties of graphs},
language = {eng},
number = {2},
pages = {591-599},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A note on on-line ranking number of graphs},
url = {http://eudml.org/doc/31051},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Semanišin, Gabriel
AU - Soták, Roman
TI - A note on on-line ranking number of graphs
JO - Czechoslovak Mathematical Journal
PY - 2006
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 56
IS - 2
SP - 591
EP - 599
AB - A $k$-ranking of a graph $G=(V,E)$ is a mapping $\varphi \:V \rightarrow \lbrace 1,2,\dots ,k\rbrace $ such that each path with endvertices of the same colour $c$ contains an internal vertex with colour greater than $c$. The ranking number of a graph $G$ is the smallest positive integer $k$ admitting a $k$-ranking of $G$. In the on-line version of the problem, the vertices $v_1,v_2,\dots ,v_n$ of $G$ arrive one by one in an arbitrary order, and only the edges of the induced graph $G[\lbrace v_1,v_2,\dots ,v_i\rbrace ]$ are known when the colour for the vertex $v_i$ has to be chosen. The on-line ranking number of a graph $G$ is the smallest positive integer $k$ such that there exists an algorithm that produces a $k$-ranking of $G$ for an arbitrary input sequence of its vertices. We show that there are graphs with arbitrarily large difference and arbitrarily large ratio between the ranking number and the on-line ranking number. We also determine the on-line ranking number of complete $n$-partite graphs. The question of additivity and heredity is discussed as well.
LA - eng
KW - on-line ranking number; complete $n$-partite graph; hereditary and additive properties of graphs; on-line ranking number; complete -partite graph; hereditary and additive properties of graphs
UR - http://eudml.org/doc/31051
ER -