Connected Colourings of Complete Graphs and Hypergraphs

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 $\left(\genfrac{}{}{0ex}{}{k}{3}\right)$ triples of colours must appear as triangles? In this note we show that the `obvious' conjecture, namely that there are always at least $\left(\genfrac{}{}{0ex}{}{k-1}{2}\right)$ 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.

Conjecture 3.5 is removed