Decompositions into spanning rainbow structures

DOI10.1112/PLMS.12245zbMATH Open1429.05024arXiv1805.07564OpenAlexW2804025813MaRDI QIDQ4973646FDOQ4973646

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)

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.

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

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

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)

Cited In (32)

• Parity of transversals of Latin squares
• 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
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Rainbow decompositions
• Maximum transversal in partial Latin squares and rainbow matchings
• Repeated patterns in proper colorings
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• Title not available (Why is that?)
• 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
• Combinatorics. Abstracts from the workshop held January 1--7, 2023
• Rainbow matchings and cycle-free partial transversals of Latin squares
• A proof of Ringel's conjecture
• Decompositions into isomorphic rainbow spanning trees
• Rainbow connectivity and rainbow criticality on graph classes
• A counterexample to Stein's equi-\(n\)-square conjecture
• New bounds for Ryser’s conjecture and related problems

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)