Decompositions into isomorphic rainbow spanning trees

Stefan Glock, Daniela Kuhn, Richard Montgomery, Deryk Osthus

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
69 Downloads (Pure)

Abstract

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph K2n, there exists a decomposition of K2n into isomorphic rainbow spanning trees. This settles conjectures of Brualdi-Hollingsworth (from 1996) and Constantine (from 2002) for large graphs.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
DOIs
Publication statusPublished - 10 Mar 2020

Keywords

  • Absorption
  • Hypergraph matchings
  • Rainbow decompositions
  • Rainbow spanning trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Decompositions into isomorphic rainbow spanning trees'. Together they form a unique fingerprint.

Cite this