On-line rankings of graphs (Q1970586)

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).