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) <= 1/2 + root 2m + 1/4, for every
hypergraph with tit edges, and that this bound is tight. Better bounds of the order
of tit 1 It log tit are proved under the assumption that the size of every edge of
H is at least 2t - 1, for some t >= 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.
Our machinery can also be applied to the hypergraphs induced by the neighbourhoods
of the vertices of a graph. It turns out that in this case we need far fewer colours.
For example, it is shown that the vertices of any graph G with maximum degree Delta
can be coloured with log(2+is an element of)Delta colours, so that the neighbourhood
of every vertex contains a point of 'unique' colour. We give an efficient deterministic
algorithm to find such a colouring, based oil a randomized algorithmic version of
the Lovasz Local Lemma, suggested by Beck, Molloy and Reed. To achieve this, we need
to (1) correct a small error in the Molloy-Reed approach, (2) restate and re-prove
their result in a deterministic form.
