A note on on-line ranking number of graphs

Semanišin, G. ; Soták, R.

Czechoslovak Mathematical Journal, Tome 56 (2006) no. 2, pp. 591-599

Résumé

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.

Détail

Classification : 05C15, 05C78, 05C85
Keywords: on-line ranking number; complete $n$-partite graph; hereditary and additive properties of graphs