JournalsjemsVol. 22, No. 10pp. 3101–3132

Embedding rainbow trees with applications to graph labelling and decomposition

  • Richard Montgomery

    University of Birmingham, UK
  • Alexey Pokrovskiy

    Birkbeck College, University of London, UK
  • Benny Sudakov

    ETH Zürich, Switzerland
Embedding rainbow trees with applications to graph labelling and decomposition cover
Download PDF

A subscription is required to access this article.


A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back more than two hundred years to the work of Euler on Latin squares. Since then rainbow structures have been the focus of extensive research and have found applications in the areas of graph labelling and decomposition. An edge-colouring is locally kk-bounded if each vertex is contained in at most kk edges of the same colour. In this paper we prove that any such edge-colouring of the complete graph K_n} contains a rainbow copy of every tree with at most (1-o(1))n/k vertices.Asalocallyvertices. As a locally kboundededgecolouringof-bounded edge-colouring of K_n mayhaveonlymay have only (n-1)/k distinctcolours,thisisessentiallytight.<p>Asacorollaryofthisresultweobtainasymptoticversionsoftwolongstandingconjecturesingraphtheory.Firstly,weproveanasymptoticversionofRingelsconjecturefrom1963,showingthatanydistinct colours, this is essentially tight.<p> As a corollary of this result we obtain asymptotic versions of two long-standing conjectures in graph theory. Firstly, we prove an asymptotic version of Ringel’s conjecture from 1963, showing that any nedgetreepacksintothecompletegraph-edge tree packs into the complete graph K_{2n+o(n)} tocoverallbutto cover all but o(n^2)$ of its edges. Secondly, we show that all trees have an almost-harmonious labelling. The existence of such a labelling was conjectured by Graham and Sloane in 1980. We also discuss some additional applications.

Cite this article

Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov, Embedding rainbow trees with applications to graph labelling and decomposition. J. Eur. Math. Soc. 22 (2020), no. 10, pp. 3101–3132

DOI 10.4171/JEMS/982