On-line rankings of graphs (Q1970586): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:24, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On-line rankings of graphs |
scientific article |
Statements
On-line rankings of graphs (English)
0 references
23 October 2000
0 references
Let \(G= (V,E)\) be a simple graph. A vertex \(k\)-ranking of \(G\) is a proper vertex coloring \(\varphi: V\to\{1,\dots, k\}\) such that every path in \(G\) with endvertices \(x\) and \(y\) of the same color \(\varphi(x)= \varphi(y)\) contains a vertex \(z\) with higher color \(\varphi(z)> \varphi(x)\). The smallest integer \(k\) for which there exists a vertex \(k\)-ranking of \(G\) is called the ranking number \(\chi_r(G)\) of \(G\). In the present paper two versions of on-line ranking are treated: (1) the graph \(G\) to be colored is specified before the on-line procedure, and (2) a class \({\mathfrak G}\) of graphs is given from which \(G\) is chosen. Here \(G\) is called on-line \(k\)-rankable if there is an algorithm that generates a vertex \(k\)-ranking of \(G\) for each possible input sequence of vertices of \(G\). Analogously \({\mathfrak G}\) is called on-line \(k\)-rankable if there is an algorithm which gives a \(k\)-rankable vertex for each \(G\in{\mathfrak G}\) and for each possible input sequence of vertices of \(G\). The on-line ranking number \(\chi^*_r(G)\) is the smallest integer \(k\) such that \(G\) is on-line \(k\)-rankable. At first the authors characterize those graphs for which a 3-ranking can be found on-line. Their results are given by three theorems: (a) For connected graphs \(G\) of order \(n\geq 4\) we have \(\chi^*_r(G)= 3\) iff \(G= S_n\), \(n\) arbitrary, or \(n= 4\) and \(G= P_4\) or \(G= C_4\); and for graphs \(G\) of order at most 3 holds \(\chi^*_r(G)= 3\) iff \(G\) has precisely three vertices (Theorem 1). (b) For graphs \(G\) which are allowed to be disconnected three cases are given which contain properties of connected complements of \(G\) (Theorem 2). (c) Two classes of graphs are given which are 3-rankable (Theorem 3). In a second part a special algorithm assigning colors to the vertices, the so-called greedy or first-fit on-line algorithm, is investigated (in each step the smallest feasible color to the next vertex is choosen). The authors prove that this algorithm generates a \((3\cdot\log_2n)\)-ranking for the paths \(P_n\), \(n\geq 2\), independent of the order the vertices arrive in (Theorem 4).
0 references
vertex coloring
0 references
on-line ranking
0 references
algorithm
0 references
paths
0 references