Publication at Faculty of Mathematics and Physics |
2006
Abstract
A coloring of points on the real line is conflict-free (wrt intervals) if for every interval containing at least one of the points there is a color occurring exactly once in that interval. We investigate on-line version, where the points are inserted one-by-one and colored at the moment of insertion.
We provide several algorithms; one of them provably uses a worst-case optimal number of colors with high probability.