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.
- Hypergraph matchings
- Rainbow decompositions
- Rainbow spanning trees
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics