Almost all optimally coloured complete graphs contain a rainbow Hamilton path

Research output: Contribution to journalArticlepeer-review

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 Kadmit 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 Kand 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 languageEnglish
Pages (from-to)57-100
Number of pages44
JournalJournal of Combinatorial Theory. Series B
Volume156
Early online date3 May 2022
DOIs
Publication statusE-pub ahead of print - 3 May 2022

Keywords

  • Andersen's conjecture
  • Edge-colouring
  • Rainbow path
  • Rainbow cycle
  • Hypergraph matchings
  • Distributive absorption
  • Latin squares

Fingerprint

Dive into the research topics of 'Almost all optimally coloured complete graphs contain a rainbow Hamilton path'. Together they form a unique fingerprint.

Cite this