Online conflict-free colorings for hypergraphs Academic Article uri icon

abstract

  • Abstract We provide a framework for online conflict-free coloring (CF-coloring) of any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF- coloring any k-degenerate hypergraph. Our algorithm uses O (k log n) colors with high probability and this bound is asymptotically optimal for any constant k. Moreover, our algorithm uses O (k log k log n) random bits with high probability. As a corollary, we obtain asymptotically optimal randomized algorithms for online CF-coloring some hypergraphs that arise in geometry. Our algorithm uses exponentially fewer random bits compared to previous results. We introduce deterministic online CF-coloring algorithms for points on the line with respect to intervals and for points on the plane with respect to halfplanes (or unit discs) that use Θ (log n) colors and recolor O (n) points in total.

publication date

  • January 1, 2007