Online coloring co-interval graphs (Q2380735)

The article is devoted to the problem of online coloring co-interval graphs. In this problem, a set of intervals on the real line is presented to the algorithm, one at a time, and upon receiving each interval \(I\), the algorithm must assign \(I\) a color different from the colors of all previously presented intervals not intersecting \(I\). The objective is to use as few colors as possible. It is known that the competitive ratio of the simple FIRST-FIT algorithm on the class of co-interval graphs is at most 2. The author shows that for the class of unit co-interval graphs, where all intervals have equal length, the 2-bound on the competitive ratio of FIRST-FIT is tight. On the other hand, the author shows that no deterministic online algorithm for coloring unit co-interval graphs can be better than 3/2-competitive. The author proves that for the class of general co-interval graphs, there is no randomized algorithm with a competitive ratio better than 3/2.