UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Embedding rainbow trees with applications to graph labelling and decomposition

Montgomery, R; Pokrovskiy, A; Sudakov, B; (2020) Embedding rainbow trees with applications to graph labelling and decomposition. Journal of the European Mathematical Society , 22 (10) pp. 3101-3132. 10.4171/jems/982. Green open access

[img]
Preview
Text
1803.03316.pdf - Accepted version

Download (381kB) | Preview

Abstract

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 k-bounded if each vertex is contained in at most k edges of the same colour. In this paper we prove that any such edge-colouring of the complete graph Kn contains a rainbow copy of every tree with at most (1−o(1))n/k vertices. As a locally k-bounded edge-colouring of Kn may have only (n − 1)/k distinct colours, this is essentially tight. 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 n-edge tree packs into the complete graph K2n+o(n) to 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.

Type: Article
Title: Embedding rainbow trees with applications to graph labelling and decomposition
Open access status: An open access version is available from UCL Discovery
DOI: 10.4171/jems/982
Publisher version: https://doi.org/10.4171/jems/982
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Rainbow subgraphs, trees, graph decomposition, graph labeling
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10112640
Downloads since deposit
7Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item