Online coloring of short intervals

We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in [1,sigma]. For sigma=1 it is the class of unit interval graphs, and for sigma=infinity the class of all interval graphs. Our focus is on intermediary classes. We present a (1+sigma)-competitive algorithm, which beats the state of the art for 1<2, and proves that the problem we study can be strictly easier than online coloring of general interval graphs. On the lower bound side, we prove that no algorithm is better than 5/3-competitive for any sigma>1, nor better than 7/4-competitive for any sigma>2, and that no algorithm beats the 5/2 asymptotic competitive ratio for all, arbitrarily large, values of sigma. That last result shows that the problem we study can be strictly harder than unit interval coloring. Our main technical contribution is a recursive composition of strategies, which seems essential to prove any lower bound higher than 2. Moreover, we prove that the natural algorithm First Fit is no better than 5/2 for any sigma >3, no better than 11/4 for any sigma >12, and finally for every epsilon >0 First Fit is no better than (5-epsilon)-competitive for any sigma > sigma epsilon(where sigma epsilon is some finite length depending on epsilon). We also give some upper bounds for FirstFit for sigma is an element of[5,13]. (c) 2024 Elsevier Ltd. All rights reserved.