Benzing, F;
Pokrovskiy, A;
Sudakov, B;
(2020)
Long directed rainbow cycles and rainbow spanning trees.
European Journal of Combinatorics
, 88
, Article 103102. 10.1016/j.ejc.2020.103102.
Preview |
Text
1711.03772v1.pdf - Accepted Version Download (345kB) | Preview |
Abstract
A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. The problem of finding rainbow subgraphs goes back to the work of Euler on transversals in Latin squares and was extensively studied since then. In this paper we consider two related questions concerning rainbow subgraphs of complete, edge-coloured graphs and digraphs. In the first part, we show that every properly edge-coloured complete directed graph contains a directed rainbow cycle of length n − O(n 4/5 ). This is motivated by an old problem of Hahn and improves a result of Gyarfas and Sarkozy. In the second part, we show that any tree T on n vertices with maximum degree ∆T ≤ βn/ log n has a rainbow embedding into a properly edge-coloured Kn provided that every colour appears at most αn times and α, β are sufficiently small constants.
| Type: | Article |
|---|---|
| Title: | Long directed rainbow cycles and rainbow spanning trees |
| Location: | Vienna, AUSTRALIA |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.ejc.2020.103102 |
| Publisher version: | https://doi.org/10.1016/j.ejc.2020.103102 |
| 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/10112639 |
Archive Staff Only
 |
View Item |
