Coloring interval graphs with First-Fit (Q1898342)

The authors investigate bounds on the performance of First-Fit on-line coloring for interval graphs with respect to the maximum cliques size. An on-line graph \(G^\triangleleft\) is a graph \(G\) together with an ordering \(\triangleleft\) of the vertices. First-Fit is the graph coloring algorithm which considers the vertices of \(G^\triangleleft\) in the order \(\triangleleft\) and colors each vertex \(x\) with the least color \(h(x) \in \{1,2, \dots\}\) such that \(h(x) \neq h(y)\) for each neighbor \(y\) of \(x\) with \(y \triangleleft x\). An on-line coloring algorithm is an algorithm that colors every vertex \(x\) of an on-line graph \(G^\triangleleft\) based only on information about the on-line graph induced by the set of vertices \(\{y \mid y \triangleleft x\) or \(y = x\}\). It is known that there exists an on-line interval graph \(G^\triangleleft\) for which First-Fit uses more than \(4.4 \omega (G^\triangleleft)\) colors, where \(\omega (G^\triangleleft)\) is the maximum size of a clique in \(G^\triangleleft\). Improving an older upper bound it is shown in this paper that for every on-line interval graph \(G^\triangleleft\) First-Fit uses at most \(25.72 \omega (G^\triangleleft)\) colors. For every on-line co-interval graph \(G^\triangleleft\) it is known that First-Fit uses at most \(2 \omega (G^\triangleleft) - 1\) colors. In this paper it is shown that for every on- line coloring algorithm \(A\) and positive integer \(k\) there exists an on- line co-interval graph \(G^\triangleleft\) with \(\omega (G^\triangleleft) = k\) and \(A\) uses at least \(2 \omega (G^\triangleleft) - 1\) colors.