Decompositions into spanning rainbow structures

DOI10.1112/PLMS.12245MaRDI QIDQ4973646zbMATH OpenOpenAlexFDO

Authors Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov

Publication date 28 November 2019

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.07564, http://pure-oai.bham.ac.uk/ws/files/59119123/rainbow_decompositions.pdf

zbMATH Keywords

decompositionHamiltonian cycletransversalperfect matchingspanning treecomplete graphrainbow subgraphrandom subgraphgeneralized Latin square

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Eulerian and Hamiltonian graphs (05C45) Orthogonal arrays, Latin squares, Room squares (05B15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Abstract: A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back more than two hundred years to the work of Euler on Latin squares and has been the focus of extensive research ever since. Euler posed a problem equivalent to finding properly $n$-edge-coloured complete bipartite graphs $K_{n,n}$ which can be decomposed into rainbow perfect matchings. While there are proper edge-colourings of $K_{n,n}$ without even a single rainbow perfect matching, the theme of this paper is to show that with some very weak additional constraints one can find many disjoint rainbow perfect matchings. In particular, we prove that if some fraction of the colour classes have at most $(1-o(1))n$ edges then one can nearly-decompose the edges of $K_{n,n}$ into edge-disjoint perfect rainbow matchings. As an application of this, we establish in a very strong form a conjecture of Akbari and Alipour and asymptotically prove a conjecture of Barat and Nagy. Both these conjectures concern rainbow perfect matchings in edge-colourings of $K_{n,n}$ with quadratically many colours. Using our techniques, we also prove a number of results on near-decompositions of graphs into other rainbow structures like Hamiltonian cycles and spanning trees. Most notably, we prove that any properly coloured complete graph can be nearly-decomposed into spanning rainbow trees. This asymptotically proves the Brualdi-Hollingsworth and Kaneko-Kano-Suzuki conjectures which predict that a perfect decomposition should exist under the same assumptions.

Recommendations

• Decompositions into isomorphic rainbow spanning trees
• Rainbow decompositions
• Rainbow spanning structures in graph and hypergraph systems
• Rainbow spanning tree decompositions in complete graphs colored by cyclic 1-factorizations
• Rainbow structures in a collection of graphs with degree conditions
• Rainbow spanning trees in properly coloured complete graphs
• Regular \(1\)-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees
• Rainbow spanning trees in abelian groups
• Rainbow spanning trees in complete graphs colored by one‐factorizations
• Edge-disjoint rainbow spanning trees in complete graphs

Cited in

(32)

• A counterexample to Stein's equi-\(n\)-square conjecture
• Parity of transversals of Latin squares
• New bounds for Ryser’s conjecture and related problems
• The \(n\)-queens completion problem
• Color isomorphic even cycles and a related Ramsey problem
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Rainbow structures in locally bounded colorings of graphs
• Maximum transversal in partial Latin squares and rainbow matchings
• Rainbow decompositions
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Repeated patterns in proper colorings
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• scientific article; zbMATH DE number 7731161 (Why is no real title available?)
• Rainbow perfect matchings in complete bipartite graphs: existence and counting
• A rainbow Dirac's theorem
• Full rainbow matchings in graphs and hypergraphs
• Rainbow Subgraphs and their Applications
• Graph and hypergraph packing
• On the number of symbols that forces a transversal
• Regular \(1\)-factorizations of complete graphs and decompositions into pairwise isomorphic rainbow spanning trees
• Pseudorandom hypergraph matchings
• Transversals in generalized Latin squares
• Almost all optimally coloured complete graphs contain a rainbow Hamilton path
• A rainbow blow-up lemma
• Graph theory. Abstracts from the workshop held January 6--12, 2019
• On the complexity of packing rainbow spanning trees
• Quaternionic 1-factorizations and complete sets of rainbow spanning trees
• Rainbow matchings and cycle-free partial transversals of Latin squares
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• A proof of Ringel's conjecture
• Decompositions into isomorphic rainbow spanning trees
• Rainbow connectivity and rainbow criticality on graph classes

This page was built for publication: Decompositions into spanning rainbow structures

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