Online hypergraph coloring

In this paper we investigate the online hypergraph coloring problem. In this online problem the algorithm receives the vertices of the hypergraph in some order v1,…,vn and it must color vi by only looking at the subhypergraph Hi=(Vi,Ei) where Vi={v1,…,vi} and Ei contains the edges of the hypergraph which are subsets of Vi. We show that there exists no online hypergraph coloring algorithm with sublinear competitive ratio. Furthermore we investigate some particular classes of hypergraphs (k-uniform hypergraphs, hypergraphs with bounded matching number, projective planes), we analyse the online algorithm FF and give matching lower bounds for these classes.