{
  "id": "1402.2087",
  "version": "v2",
  "published": "2014-02-10T10:22:15.000Z",
  "updated": "2014-02-20T22:57:40.000Z",
  "title": "Connected Colourings of Complete Graphs and Hypergraphs",
  "authors": [
    "Imre Leader",
    "Ta Sheng Tan"
  ],
  "comment": "Conjecture 3.5 is removed",
  "categories": [
    "math.CO"
  ],
  "abstract": "Gallai's colouring theorem states that if the edges of a complete graph are 3-coloured, with each colour class forming a connected (spanning) subgraph, then there is a triangle that has all 3 colours. What happens for more colours: if we $k$-colour the edges of the complete graph, with each colour class connected, how many of the $\\binom{k}{3}$ triples of colours must appear as triangles? In this note we show that the `obvious' conjecture, namely that there are always at least $\\binom{k-1}{2}$ triples, is not correct. We determine the minimum asymptotically. This answers a question of Johnson. We also give some results about the analogous problem for hypergraphs, and we make a conjecture that we believe is the `right' generalisation of Gallai's theorem to hypergraphs.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2014-02-20T22:57:40.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complete graph",
      "connected colourings",
      "hypergraphs",
      "gallais colouring theorem states",
      "gallais theorem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1402.2087L"
    }
  }
}