Online conflict-free coloring of intervals

In this paper, we study the problem of online conflict-free coloring of intervals on a line, where each newly inserted interval must be assigned a color upon insertion such that the coloring remains conflict-free, i.e. for each point p in the union of the current intervals, there must be an interval I with a unique color among all intervals covering p. We fi rst present a simple algorithm which uses O(pn) colors where n is the number of current intervals. Next, we propose an CF-coloring of intervals which uses O(log3 n) colors.