Online coloring of hypergraphs
We give a tight bound on randomized online coloring of hypergraphs. The bound holds even if the algorithm knows the hypergraph in advance (but not the ordering in which it is presented). More specifically, we show that for any n and k, there is a 2-colorable k-uniform hypergraph on n vertices for which any randomized online coloring uses Omega(n/k) colors in expectation. (C) 2010 Elsevier B.V. All rights reserved.
hypergraphs online algorithms graph coloring