Decompositions into isomorphic rainbow spanning trees

Research output: Contribution to journalArticle

Colleges, School and Institutes

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.

Details

Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Publication statusPublished - 10 Mar 2020

Keywords

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