Linearly many rainbow trees in properly edge-coloured complete graphs

DOI10.1016/J.JCTB.2018.03.005zbMATH Open1391.05116arXiv1703.07301OpenAlexW2609209176WikidataQ130069422 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)

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.

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

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

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)

Cites Work

• A Combinatorial Theorem
• Edge-disjoint rainbow spanning trees in complete graphs
• Rainbow spanning trees in complete graphs colored by one‐factorizations
• Multicolored trees in complete graphs
• Multicolored trees in complete graphs
• Title not available (Why is that?)
• Kotzig Factorizations: Existence and Computational Results
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
• Spanning trees orthogonal to one-factorizations of \(K_{2n}\).
• Multicolored isomorphic spanning trees in complete graphs.
• Title not available (Why is that?)
• Multicolored Parallelisms of Isomorphic Spanning Trees
• Properly colored and rainbow copies of graphs with few cherries

Cited In (21)

• Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations
• Color isomorphic even cycles and a related Ramsey problem
• Rainbow structures in locally bounded colorings of graphs
• Properly colored and rainbow copies of graphs with few cherries
• Rainbow spanning trees in properly coloured complete graphs
• Edge-disjoint rainbow trees in properly coloured complete graphs
• Repeated patterns in proper colorings
• Title not available (Why is that?)
• On rainbow trees and cycles
• \((g,f)\)-chromatic spanning trees and forests
• Embedding rainbow trees with applications to graph labelling and decomposition
• Regular \(1\)-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees
• On the number of rainbow spanning trees in edge-colored complete graphs
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• A rainbow blow-up lemma
• On the complexity of packing rainbow spanning trees
• Quaternionic 1-factorizations and complete sets of rainbow spanning trees
• Long directed rainbow cycles and rainbow spanning trees
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• Decompositions into isomorphic rainbow spanning trees
• 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)