Pokrovskiy, A;
Sudakov, B;
(2018)
Linearly many rainbow trees in properly edge-coloured complete graphs.
Journal of Combinatorial Theory, Series B
, 132
pp. 134-156.
10.1016/j.jctb.2018.03.005.
Preview |
Text
1703.07301v3.pdf - Accepted Version Download (508kB) | Preview |
Abstract
A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. The study of rainbow decompositions has a long history, going back to the work of Euler on Latin squares. In this paper we discuss three problems about decomposing complete graphs into rainbow trees: the Brualdi-Hollingsworth Conjecture, Constantine’s Conjecture, and the Kaneko-Kano-Suzuki Conjecture. We show that in every proper edge-colouring of Kn there are 10−6n edge-disjoint spanning isomorphic rainbow trees. This simultaneously improves the best known bounds on all these conjectures. Using our method we also show that every properly (n − 1)-edge-coloured Kn has n/9 − 6 edge-disjoint rainbow trees, giving further improvement on the Brualdi-Hollingsworth Conjecture
| Type: | Article |
|---|---|
| Title: | Linearly many rainbow trees in properly edge-coloured complete graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.jctb.2018.03.005 |
| Publisher version: | https://doi.org/10.1016/j.jctb.2018.03.005 |
| 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 trees, proper edge-colourings, graph decompositions. |
| UCL classification: | UCL 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/10112650 |
Archive Staff Only
 |
View Item |
