Connected colourings of complete graphs and hypergraphs (Q5964989)

An edge-colouring of the complete graph \(K_n\) is connected if each colour class forms a connected spanning subgraph. Gallai's colouring theorem [\textit{T. Gallai}, Acta Math. Acad. Sci. Hung. 18, 25--66 (1967; Zbl 0153.26002)] states that every connected 3-colouring of \(K_n\) contains a rainbow triangle, that is a triangle using three distinct colours. In this paper, the authors consider the following general question [\textit{P. Johnson}, Research problems: Problem 277 (BCC15.7). Edge-colourings of complete graphs. Discrete Math. 608, 167--168 (2004)]: How many of the \(k \choose 3\) triples of colours must appear as triangles in a connected \(k\)-colouring of \(K_n\)? They prove that \(f(k)=\frac{k(k-2)}{3}\) when \(2k+1\) is a prime and that \(f(k)=\frac{k^2}{3}\big(1+o(1)\big)\) for general \(k\). Moreover, they conjecture that the right answer is \(\left\lceil\frac{k(k-2)}{3}\right\rceil\) for all \(k\geq 3\). They also discuss analogues of these results for 3-uniform hypergraphs according to different notions of connectedness.