Rainbow spanning trees in properly coloured complete graphs

J Balogh, H Liu, R Montgomery - Discrete Applied Mathematics, 2018 - Elsevier
Discrete Applied Mathematics, 2018Elsevier
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 Ω (n) pairwise …
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 Ω (n) pairwise edge-disjoint rainbow spanning trees. Independently, Pokrovskiy and Sudakov recently proved that every properly edge-coloured K n contains Ω (n) isomorphic pairwise edge-disjoint rainbow spanning trees.
Elsevier
以上显示的是最相近的搜索结果。 查看全部搜索结果