We consider the problem of coloring a unit interval graph dynamically.
Intervals arrive one after the other and have to be colored immediately
such that no two intervals of the same color overlap. In each step, only
a limited number of intervals may be recolored to maintain a proper
coloring (thus interpolating between the well-studied online and offline
settings). The number of allowed recolorings per step is the so-called
recourse budget. In addition, I will discuss issues related to the
chromatic number of unit circular arc graphs, which are closely related
to the above problem.
This is joint work with Anna Zych-Pawlewicz.