An on-line graph coloring algorithm with sublinear performance ratio (Q1124602)

In an on-line graph algorithm the graph is presented one vertex at a time. Each new vertex is given together with all edges joining it to previous vertices. An on-line coloring algorithm assigns a color (positive integer) to each vertex as it is received and, once assigned, the color cannot be changed. If the integer assigned is always the least possible, the algorithm is the first-fit algorithm. If A is any graph coloring algorithm then, for a graph G, \(\chi_ A(G)\) denotes the number of colors that A uses to color G. The performance ratio of A on G, denoted by \(\rho_{A(G)}\), is \(\chi_{A(G)}/\chi (G).\) The performance function of A is defined to be the maximum of \(\rho_{A(n)}\) over all graphs of order n. The authors report that Szegedy (unpublished) has recently shown that for any on-line algorithm A and integer \(\kappa\), there is a graph on at most \(\kappa (2^{\kappa}-1)\) vertices having chromatic number \(\kappa\), but for which the algorithm A requires \(2^{\kappa}-1\) colors. Thus the performance function for any on-line algorithm A grows at least as fast as n/(log n)\({}^ 2\). The authors demonstrate the existence of an on-line coloring algorithm with performance function \((2n/\log^*n)(1+o(1))\) where \(\log^*n\) is the smallest \(\kappa\) for which the \(\kappa\) times iterated logarithm, base 2, is at most 1.