Conflict-free colorings of graphs and hypergraphs Probability and Computing

A colouring of the vertices of a hypergraph H is called conflict-free if each hyperedge E of H contains a vertex of 'unique' colour that does not get repeated in E. The smallest number of colours required for such a colouring is called the conflict-free chromatic number of H, and is denoted by chi(CF)(H). This parameter wits first introduced by Even, Lotker, Ron and Smorodinsky (FOCS 2002) in a geometric setting, in connection with frequency assignment problems for cellular networks. Here we analyse this notion for general hypergraphs. It is shown that chi(CF)(H) = 3. Using Lovasz's Local Lemma, the same result holds for hypergraphs in which the size of every edge is at least 2t - 1 and every edge intersects at most tit others. We give efficient polynomial-time algorithms to obtain such colourings.