TY - JOUR
T1 - Rainbow spanning trees in properly coloured complete graphs
AU - Balogh, József
AU - Liu, Hong
AU - Montgomery, Richard
N1 - Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/10/1
Y1 - 2018/10/1
N2 - 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 Kn 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 Kn. Improving the previous best known bound, we show that every properly edge-coloured Kn contains Ω(n) pairwise edge-disjoint rainbow spanning trees. Independently, Pokrovskiy and Sudakov recently proved that every properly edge-coloured Kn contains Ω(n) isomorphic pairwise edge-disjoint rainbow spanning trees.
AB - 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 Kn 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 Kn. Improving the previous best known bound, we show that every properly edge-coloured Kn contains Ω(n) pairwise edge-disjoint rainbow spanning trees. Independently, Pokrovskiy and Sudakov recently proved that every properly edge-coloured Kn contains Ω(n) isomorphic pairwise edge-disjoint rainbow spanning trees.
KW - Rainbow subgraph
KW - Spanning trees
UR - http://www.scopus.com/inward/record.url?scp=85045106558&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85045106558&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2018.03.066
DO - 10.1016/j.dam.2018.03.066
M3 - Article
AN - SCOPUS:85045106558
SN - 0166-218X
VL - 247
SP - 97
EP - 101
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -