← All problems

Brualdi–Hollingsworth conjecture on rainbow spanning-tree decompositions

14 years old · documented by

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, and a collection of subgraphs decomposes KnK_n if its members are edge-disjoint and cover every edge. Brualdi–Hollingsworth conjecture. For all n>4n>4 and any 11-factorization of KnK_n, there exists a decomposition of KnK_n into rainbow spanning trees. The condition n>4n>4 is necessary. The conjecture asks for a full decomposition, strengthening the known results guaranteeing only finitely or linearly many edge-disjoint rainbow spanning trees; an asymptotic version was known, while the paper's main theorem proves the conjecture for sufficiently large nn.

References

3 papers in this index state this conjecture (2011–2019). The statement above is taken from the most recent of them; the others are arXiv:1703.07301, arXiv:1102.4802.

Source: Stefan Glock, Daniela Kühn, Richard Montgomery and Deryk Osthus, “Decompositions into isomorphic rainbow spanning trees”, arXiv:1903.04262 (2020).

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.