(2, 2)-colourings and clique-free σ-hypergraphs

Abstract

We consider vertex colourings of r-uniform hypergraphs H in the classical sense, that is such that no edge has all its vertices given the same colour, and (2, 2)-colourings of H in which the vertices in any edge are given exactly two colours. This is a special case of constrained colourings introduced by Bujtas and Tuza which, in turn, is a generalization of Voloshin’s colourings of mixed hypergraphs. We study, χ (H), the classical chromatic number, and the (2, 2)-spectrum of H, that is, the set of integers k for which H has a (2, 2)- colouring using exactly k colours. We present extensions of hypergraphs which preserve both the chromatic number and the (2, 2)-spectrum and which, however often repeated, do not increase the clique number of H by more than a fixed number. In particular, we present sparse (2, 2)-colourable clique-free σ-hypergraphs having arbitrarily large chromatic number—these r-uniform hypergraphs were studied by the authors in earlier papers. We use these ideas to extend some known 3-uniform hypergraphs which exhibit a (2, 2)-spectrum with remarkable gaps. We believe that this work is the first to present an extension of hypergraphs which preserves both χ (H) and the (2, 2)-spectrum of H simultaneously.