Constantine's multicoloured tree parallelism conjecture
Constantine's multicoloured tree parallelism conjecture
Let be a complete graph and let a -factorization be an edge-colouring whose colour classes form a decomposition of into perfect matchings. A subgraph is rainbow if all its edges have distinct colours. A multicoloured tree parallelism (MTP) is a decomposition of an edge-coloured into isomorphic rainbow spanning trees. Constantine's conjecture. For all , any -factorization of admits a decomposition into isomorphic rainbow spanning trees. This strengthens the Brualdi–Hollingsworth conjecture by requiring all trees in the decomposition to be isomorphic. The source reports only weak asymptotic results before the paper; its main theorem proves the conjecture for sufficiently large .
Sources & referencesView supporting material
Primary source
Stefan Glock, Daniela Kühn, Richard Montgomery and Deryk Osthus, “Decompositions into isomorphic rainbow spanning trees”, arXiv:1903.04262 (2020).
Additional references
3 papers in this index state this conjecture (2017–2019). The statement above is taken from the most recent of them; the others are arXiv:1805.07564, arXiv:1703.07301.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.