Pokrovskiy, A;
Sudakov, B;
(2017)
Edge-disjoint rainbow trees in properly coloured complete graphs.
Electronic Notes in Discrete Mathematics
, 61
pp. 995-1001.
10.1016/j.endm.2017.07.064.
Preview |
Text
rainbow-trees-eurocomb.pdf - Accepted Version Download (214kB) | 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. We discuss three problems about decomposing complete graphs into rainbow trees: the Brualdi-Hollingsworth Conjecture, Constantine’s Conjecture, and the Kaneko-Kano-Suzuki Conjecture. The main result which we discuss is that in every proper edge-colouring of Kn there are 10−6n edge-disjoint isomorphic spanning rainbow trees. This simultaneously improves the best known bounds on all these conjectures. Using our method it is also possible to show that every properly (n−1)-edge-coloured Kn has n/9 edge-disjoint spanning rainbow trees, giving a further improvement on the Brualdi-Hollingsworth Conjecture
| Type: | Article |
|---|---|
| Title: | Edge-disjoint rainbow trees in properly coloured complete graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.endm.2017.07.064 |
| Publisher version: | https://doi.org/10.1016/j.endm.2017.07.064 |
| 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. |
| 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/10112656 |
Archive Staff Only
 |
View Item |
