Selective hypergraph colourings

Abstract

We look at colourings of r-uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge E in an r-uniform hypergraph H whose vertices are coloured is the partition of r induced by the colour classes of the vertices in E. Let Q be a set of partitions of r. A Q-colouring of H is a colouring of its vertices such that only patterns appearing in Q are allowed. We first show that many known hypergraph colouring problems, including Ramsey theory, can be stated in the language of Q-colourings. Then, using as our main tools the notions of Q-colourings and Σ-hypergraphs, we define and prove a result on tight colourings, which is a strengthening of the notion of unique colourability. Σ-hypergraphs are a natural generalisation of σ-hypergraphs introduced by the first two authors in an earlier paper. We also show that there exist Σ-hypergraphs with arbitrarily large Q-chromatic number and chromatic number but with bounded clique number. Dvořák et al. have characterised those Q which can lead to a hypergraph with a gap in its Q-spectrum. We give a short direct proof of the necessity of their condition on Q. We also prove a partial converse for the special case of Σ-hypergraphs. Finally, we show that, for at least one family Q which is known to yield hypergraphs with gaps, there exist no Σ-hypergraphs with gaps in their Q-spectrum.