Decompositions into isomorphic rainbow spanning trees

Stefan Glock; Daniela Kuhn; Richard Montgomery; Deryk Osthus

doi:10.1016/j.jctb.2020.03.002

Decompositions into isomorphic rainbow spanning trees

Stefan Glock, Daniela Kuhn, Richard Montgomery, Deryk Osthus

Mathematics

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

1 Citation (Scopus)

110 Downloads (Pure)

Abstract

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph K_2n, there exists a decomposition of K_2n into isomorphic rainbow spanning trees. This settles conjectures of Brualdi-Hollingsworth (from 1996) and Constantine (from 2002) for large graphs.

Original language	English
Pages (from-to)	439-484
Journal	Journal of Combinatorial Theory. Series B
Volume	146
DOIs	https://doi.org/10.1016/j.jctb.2020.03.002
Publication status	Published - 10 Mar 2020

Keywords

Absorption
Hypergraph matchings
Rainbow decompositions
Rainbow spanning trees

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2020.03.002Licence: None: All rights reserved

Glock_et_al_Decompositions_into_isomorphic_rainbow_spanning_trees_JCTB_2020Accepted author manuscript, 620 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivs (CC BY-NC-ND)

https://www.sciencedirect.com/science/article/pii/S0095895620300113Licence: None: All rights reserved

Cite this

@article{5f8dcea60b7841f693224be92a79f1b8,

title = "Decompositions into isomorphic rainbow spanning trees",

abstract = "A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph K2n, there exists a decomposition of K2n into isomorphic rainbow spanning trees. This settles conjectures of Brualdi-Hollingsworth (from 1996) and Constantine (from 2002) for large graphs.",

keywords = "Absorption, Hypergraph matchings, Rainbow decompositions, Rainbow spanning trees",

author = "Stefan Glock and Daniela Kuhn and Richard Montgomery and Deryk Osthus",

year = "2020",

month = mar,

day = "10",

doi = "10.1016/j.jctb.2020.03.002",

language = "English",

volume = "146",

pages = "439--484",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Elsevier",

}

TY - JOUR

T1 - Decompositions into isomorphic rainbow spanning trees

AU - Glock, Stefan

AU - Kuhn, Daniela

AU - Montgomery, Richard

AU - Osthus, Deryk

PY - 2020/3/10

Y1 - 2020/3/10

N2 - A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph K2n, there exists a decomposition of K2n into isomorphic rainbow spanning trees. This settles conjectures of Brualdi-Hollingsworth (from 1996) and Constantine (from 2002) for large graphs.

AB - A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. Our main result implies that, given any optimal colouring of a sufficiently large complete graph K2n, there exists a decomposition of K2n into isomorphic rainbow spanning trees. This settles conjectures of Brualdi-Hollingsworth (from 1996) and Constantine (from 2002) for large graphs.

KW - Absorption

KW - Hypergraph matchings

KW - Rainbow decompositions

KW - Rainbow spanning trees

UR - http://www.scopus.com/inward/record.url?scp=85081260306&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2020.03.002

DO - 10.1016/j.jctb.2020.03.002

M3 - Article

SN - 0095-8956

VL - 146

SP - 439

EP - 484

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Decompositions into isomorphic rainbow spanning trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this