Online coloring of short intervals
Joanna Chybowska-Sokół, Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Patryk Mikos, Adam Polak · European Journal of Combinatorics · 2024
We study the online graph coloring problem restricted to the intersection graphs of intervals with lengths in [ 1 , σ ] . For σ = 1 it is the class of unit interval graphs and for σ = ∞ the class of all interval graphs. Our focus is on intermediary classes. We present a ( 1 + σ ) -competitive algorithm, which beats the state of the art for 1 1 , nor better than 7 / 4 -competitive for any σ > 2 , and that no algorithm beats the 5 / 2 asymptotic competitive ratio for all, arbitrarily large, values of σ . 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 FirstFit is no better than 5 / 2 for any σ > 3 , no better than 11 / 4 for any σ > 12 , and finally for every ɛ ɛ > 0 FirstFit is no better than ɛ ( 5 − ɛ ) -competitive for any ɛ σ > σ ɛ (where ɛ σ ɛ is some finite length depending on ɛ ɛ ). We also give some upper bounds for FirstFit for σ ∈ [ 5 , 13 ] .