pith. sign in

arxiv: 1704.07200 · v1 · pith:XQW5ZBKFnew · submitted 2017-04-24 · 🧮 math.CO

Rainbow spanning trees in properly coloured complete graphs

classification 🧮 math.CO
keywords properlyrainbowedge-colouredspanningtreesedge-disjointeverypairwise
0
0 comments X
read the original abstract

In this short note, we study pairwise edge-disjoint rainbow spanning trees in properly edge-coloured complete graphs, where a graph is rainbow if its edges have distinct colours. Brualdi and Hollingsworth conjectured that every $K_n$ properly edge-coloured by $n-1$ colours has $n/2$ edge-disjoint rainbow spanning trees. Kaneko, Kano and Suzuki later suggested this should hold for every properly edge-coloured $K_n$. Improving the previous best known bound, we show that every properly edge-coloured $K_n$ contains $\Omega(n)$ pairwise edge-disjoint rainbow spanning trees. Independently, Pokrovskiy and Sudakov recently proved that every properly edge-coloured $K_n$ contains $\Omega(n)$ isomorphic pairwise edge-disjoint rainbow spanning trees.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.