{
  "id": "1402.3057",
  "version": "v1",
  "published": "2014-02-13T08:20:04.000Z",
  "updated": "2014-02-13T08:20:04.000Z",
  "title": "$(2,2)$-colourings and clique-free $σ$-hypergraphs",
  "authors": [
    "Yair Caro",
    "Josef Lauri",
    "Christina Zarb"
  ],
  "categories": [
    "math.CO"
  ],
  "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 generalisation of Voloshin's colourings of mixed hypergraphs. We study, $\\chi(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 $\\sigma$-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 $\\chi(H)$ and the $(2,2)$-spectrum of $H$ simultaneously.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-02-13T08:20:04.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C65"
    ],
    "keywords": [
      "uniform hypergraphs",
      "clique-free",
      "arbitrarily large chromatic number",
      "vertex colourings",
      "classical chromatic number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1402.3057C"
    }
  }
}