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

triples of colours must appear as triangles? In this note we show that the `obvious' conjecture, namely that there are always at least

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.

Review text

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.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Connected colourings of complete graphs and hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964989)