Hamid Zarrabi-Zadeh - School of Computer Science, University of Waterloo Waterloo, Ontario, Canada, N۲L ۳G۱

We study the problem of online coloring co-interval graphs. In this problem, a set of intervals on the real line is presented to the online algorithm in some arbitrary order, and the algorithm must assign each interval a color that is diferent from the colors of all previously presented intervals not intersecting the current interval. It is known that the competitive ratio of the simple First-Fit algorithm on the class of co-interval graphs is at most 2.We show 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, we show that no deterministic online algorithm for coloring unit co-interval graphs can be better than 3/2-competitive. We then study the e®ect of randomization in our problem, and prove a lower bound of 4/3 on the competitive ratio of any randomized algorithm for the unit co-interval coloring problem. We also prove that for the class of general co-interval graphs no randomized algorithm has competitive ratio better than 3/2.

Online Algorithms, Graph Coloring, Co-interval Graphs