Conflict-Free Colourings of Uniform Hypergraphs With Few Edges

Source abstract

A colouring of the vertices of a hypergraph is called conflict-free if each edge e of contains a vertex whose colour does not repeat in e . The smallest number of colours required for such a colouring is called the conflict-free chromatic number of , and is denoted by χ CF ( ). Pach and Tardos proved that for an (2 r − 1)-uniform hypergraph with m edges, χ CF ( ) is at most of the order of rm 1/ r log m , for fixed r and large m . They also raised the question whether a similar upper bound holds for r -uniform hypergraphs. In this paper we show that this is not necessarily the case. Furthermore, we provide lower and upper bounds on the minimum number of edges of an r -uniform simple hypergraph that is not conflict-free k -colourable.