Complete colourings of hypergraphs

A complete c-colouring of a graph is a proper colouring in which every pair of distinct colours from [c] = {1, 2, . . . , c} appears as the colours of endvertices of some edge. We consider the following generalisation of this concept to uniform hypergraphs. A complete c-colouring for a k-uniform hypergraph H is a mapping from the vertex set of H to [c], such that (i) the colour set used on each edge has exactly k elements, and (ii) every k-element subset of [c] appears as the colour set of some edge. In this paper we exhibit some differences between complete colourings of graphs and hypergraphs. First, it is known that every graph has a complete c-colouring for some c. In contrast, we show an infinite family of hypergraphs H that do not admit a complete c-colouring for any c. We also extend this construction to λ-complete colourings (for 0 < λ ≤ 1), where condition (ii) is substituted with: at least λ c k different colour sets appear on edges. We establish upper and lower bounds on a maximum degree, which guarantees the existence of a complete colouring of any hypergraph. Moreover, we prove that it is NPcomplete to determine if a given hypergraph has a λ-complete colouring. Next, we show that, unlike graphs, hypergraphs do not have the so-called interpolation property, i.e., we construct hypergraphs that have a complete r-colouring and a complete s-colouring, but no complete t-colouring for some t such that r < t < s. Finally, we investigate the notion of λ-complete colourings of graphs (i.e., 2-uniform hypergraphs). We show that λ-complete colourings have the same interpolation property as complete colourings. Moreover, we prove that it is NP-complete to decide whether a tree with c 2 edges has a λ-complete c-colouring, which strengthens the result by Cairnie and Edwards [JGT, 1997]