Rainbow spanning trees in properly coloured complete graphs

József Balogh; Hong Liu; Richard Montgomery

doi:10.1016/j.dam.2018.03.066

Rainbow spanning trees in properly coloured complete graphs

József Balogh, Hong Liu, Richard Montgomery

Mathematics

Research output: Contribution to journal › Article › peer-review

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 Ω(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.

Original language	English (US)
Pages (from-to)	97-101
Number of pages	5
Journal	Discrete Applied Mathematics
Volume	247
DOIs	https://doi.org/10.1016/j.dam.2018.03.066
State	Published - Oct 1 2018

Keywords

Rainbow subgraph
Spanning trees

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.1016/j.dam.2018.03.066

Library availability

Discover UIUC Full Text

Cite this

@article{2e69b7b756984f6591922353b632bc78,

title = "Rainbow spanning trees in properly coloured complete graphs",

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 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.",

keywords = "Rainbow subgraph, Spanning trees",

author = "J{\'o}zsef Balogh and Hong Liu and Richard Montgomery",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = oct,

day = "1",

doi = "10.1016/j.dam.2018.03.066",

language = "English (US)",

volume = "247",

pages = "97--101",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Rainbow spanning trees in properly coloured complete graphs

AU - Balogh, József

AU - Liu, Hong

AU - Montgomery, Richard

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 -

Rainbow spanning trees in properly coloured complete graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this