Generalised online colouring problems in overlap graphs

Marc Demange*, Martin Olsen

*Corresponding author for this work

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review


In this paper we consider an online version of different colouring problems in overlap graphs, motivated by some stacking problems. The instance is a system of time intervals presented in non-decreasing order of the left endpoint. We consider the usual colouring problem as well as b-bounded colouring (colour class have a maximum capacity b) and the same problems in the complement graph. We also consider the case where at most b intervals of the same colour can intersect. For all these versions we obtain a logarithmic competitive ratio w.r.t. the maximum ratio of interval lengths while the best known ratio for the usual colouring was linear. To our knowledge it is the first time the other variants are considered in online overlap graphs. Moreover, in the offline case, a pre-processing allows us to deduce a logarithmic approximation ratio w.r.t. the maximum number of pairwise disjoint intervals in the system. 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. We think that this new partition problem by itself is of interest for future work.

Original languageEnglish
JournalTheoretical Computer Science
Pages (from-to)58-73
Number of pages16
Publication statusPublished - Jul 2021


  • Approximation algorithms
  • Competitive preserving reduction
  • Online colouring
  • Overlap graphs
  • Permutation graphs


Dive into the research topics of 'Generalised online colouring problems in overlap graphs'. Together they form a unique fingerprint.

Cite this