We consider an online version of the conflict-free coloring
problem. In one dimension we are given a sequence of points on the
line. Each newly inserted point must be assigned a color upon
insertion, and at all times the coloring has to be
conflict-free, in the sense that in every interval I there is a
color that appears exactly once. The goal is to minimize the
number of colors used.

We present several deterministic and randomized algorithms for
achieving this goal, and bound the number of colors they use. If time
allows I will also talk about more recent results for analogous
problems in the plane.

Joint work with Amos Fiat, Meital Levy, Jiri Matousek, Elchanan
Mossel, Janos Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo
Welzl.