We consider online versions of different colouring problems in interval overlap graphs, motivated by stacking problems. An instance is a system of time intervals presented in non-decreasing order of the left endpoints. We consider the usual colouring problem as well as b-bounded colouring and the same problems in the complement graph. We also consider the case where at most b intervals of the same colour can include the same element. For these versions, we obtain a logarithmic competitive ratio with respect to the maximum ratio of interval lengths. The best known ratio for the usual colouring was linear, and to our knowledge other variants have not been considered. Moreover, pre-processing allows us to deduce approximation results in the offline case. Our method is based on a partition of the overlap graph into permutation graphs, leading to a competitive-preserving reduction of the problem in overlap graphs to the same problem in permutation graphs. This new partition problem by itself is of interest for future work.
展开▼
