Dynamic and kinetic conflict-free coloring of intervals with respect to points

We introduce the dynamic conflict-free coloring problem for a set S of intervals in R 1 with respect to points, where the goal is to maintain a conflict-free coloring for S under insertions and deletions. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: \u3cbr/\u3e- a lower bound on the number of recolorings as a function of the number of colors, which implies that with O(1) recolorings per update the worst-case number of colors is Ω(logn/loglogn) , and that any strategy using O(1/ε) colors needs Ω(εn ε ) recolorings; \u3cbr/\u3e- a coloring strategy that uses O(logn) colors at the cost of O(logn) recolorings, and another strategy that uses O(1/ε) colors at the cost of O(n ε /ε) recolorings; \u3cbr/\u3e- stronger upper and lower bounds for special cases. \u3cbr/\u3eWe also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight