Constantine's multicoloured tree parallelism conjecture

Let KnK_n be a complete graph and let a 11-factorization be an edge-colouring whose colour classes form a decomposition of KnK_n 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 KnK_n into isomorphic rainbow spanning trees. Constantine's conjecture. For all n>4n>4, any 11-factorization of KnK_n 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 nn.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.