Abstract
A subgraph H of an edge-coloured graph is called rainbow if all of the edges of H have different colours. In 1989, Andersen conjectured that every proper edge-colouring of Kn admits a rainbow path of length n-2. We show that almost all optimal edge-colourings of Kn admit both (i) a rainbow Hamilton path and (ii) a rainbow cycle using all of the colours. This result demonstrates that Andersen's Conjecture holds for almost all optimal edge-colourings of Kn and answers a recent question of Ferber, Jain, and Sudakov. Our result also has applications to the existence of transversals in random symmetric Latin squares.
Original language | English |
---|---|
Pages (from-to) | 57-100 |
Number of pages | 44 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 156 |
Early online date | 3 May 2022 |
DOIs | |
Publication status | E-pub ahead of print - 3 May 2022 |
Keywords
- Andersen's conjecture
- Edge-colouring
- Rainbow path
- Rainbow cycle
- Hypergraph matchings
- Distributive absorption
- Latin squares