Rainbow spanning trees in properly coloured complete graphs

József Balogh, Hong Liu, Richard Montgomery

Research output: Contribution to journalArticlepeer-review

Abstract

In this short note, we study pairwise edge-disjoint rainbow spanning trees in properly edge-coloured complete graphs, where a graph is rainbow if its edges have distinct colours. Brualdi and Hollingsworth conjectured that every Kn properly edge-coloured by n−1 colours has n∕2 edge-disjoint rainbow spanning trees. Kaneko, Kano and Suzuki later suggested this should hold for every properly edge-coloured Kn. Improving the previous best known bound, we show that every properly edge-coloured Kn contains Ω(n) pairwise edge-disjoint rainbow spanning trees. Independently, Pokrovskiy and Sudakov recently proved that every properly edge-coloured Kn contains Ω(n) isomorphic pairwise edge-disjoint rainbow spanning trees.

Original languageEnglish (US)
Pages (from-to)97-101
Number of pages5
JournalDiscrete Applied Mathematics
Volume247
DOIs
StatePublished - Oct 1 2018

Keywords

  • Rainbow subgraph
  • Spanning trees

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Rainbow spanning trees in properly coloured complete graphs'. Together they form a unique fingerprint.

Cite this