Linearly many rainbow trees in properly edge-coloured complete graphs

DOI10.1016/J.JCTB.2018.03.005zbMATH Open1391.05116OpenAlexW2609209176WikidataQ130069422 ScholiaQ130069422MaRDI QIDQ723883FDOQ723883

Authors Alexey Pokrovskiy, Benny Sudakov 

Publication date 24 July 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.07301

zbMATH Keywords

graph decompositionsproper edge-colouringsrainbow trees

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A subgraph of an edge-coloured complete graph is called rainbow if all its edges have different colours. The study of rainbow decompositions has a long history, going back to the work of Euler on Latin squares. In this paper we discuss three problems about decomposing complete graphs into rainbow trees: the Brualdi-Hollingsworth Conjecture, Constantine's Conjecture, and the Kaneko-Kano-Suzuki Conjecture. We show that in every proper edge-colouring of $K_n$ there are $10^{-6}n$ edge-disjoint spanning isomorphic rainbow trees. This simultaneously improves the best known bounds on all these conjectures. Using our method we also show that every properly $(n-1)$-edge-coloured $K_n$ has $n/9$ edge-disjoint rainbow trees, giving further improvement on the Brualdi-Hollingsworth Conjecture.

Recommendations

• Edge-disjoint rainbow trees in properly coloured complete graphs
• Rainbow spanning trees in properly coloured complete graphs
• Decompositions into isomorphic rainbow spanning trees
• Edge-disjoint rainbow spanning trees in complete graphs
• On the number of rainbow spanning trees in edge-colored complete graphs

Cites work

• scientific article; zbMATH DE number 53885 (Why is no real title available?)
• scientific article; zbMATH DE number 1753164 (Why is no real title available?)
• A Combinatorial Theorem
• Edge-disjoint rainbow spanning trees in complete graphs
• Kotzig Factorizations: Existence and Computational Results
• Multicolored Parallelisms of Isomorphic Spanning Trees
• Multicolored isomorphic spanning trees in complete graphs.
• Multicolored trees in complete graphs
• Multicolored trees in complete graphs
• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
• Rainbow spanning trees in complete graphs colored by one‐factorizations
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• Spanning trees orthogonal to one-factorizations of \(K_{2n}\).

Cited in

(20)

• Color isomorphic even cycles and a related Ramsey problem
• On the number of rainbow spanning trees in edge-colored complete graphs
• \((g,f)\)-chromatic spanning trees and forests
• scientific article; zbMATH DE number 7731161 (Why is no real title available?)
• On the complexity of packing rainbow spanning trees
• Rainbow spanning trees in properly coloured complete graphs
• Quaternionic 1-factorizations and complete sets of rainbow spanning trees
• Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations
• Regular \(1\)-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees
• A rainbow blow-up lemma
• Rainbow structures in locally bounded colorings of graphs
• Edge-disjoint rainbow trees in properly coloured complete graphs
• Decompositions into isomorphic rainbow spanning trees
• Repeated patterns in proper colorings
• Embedding rainbow trees with applications to graph labelling and decomposition
• Long directed rainbow cycles and rainbow spanning trees
• On rainbow trees and cycles
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• An algorithmic proof of the Lovász local lemma via resampling oracles

This page was built for publication: Linearly many rainbow trees in properly edge-coloured complete graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q723883)