Rainbow structures in locally bounded colorings of graphs

DOI10.1002/rsa.20902zbMath1450.05070arXiv1805.08424OpenAlexW3000588731WikidataQ126356626 ScholiaQ126356626MaRDI QIDQ5128755

Deryk Osthus, Daniela Kühn, Andrey B. Kupavskii, Jae-Hoon Kim

Publication date: 26 October 2020

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Latin squaresHamilton cyclesspanning treesrainbow colorings

Mathematics Subject Classification ID

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

Related Items

The \(n\)-queens completion problem ⋮ The Erdős matching conjecture and concentration inequalities ⋮ On odd rainbow cycles in edge-colored graphs ⋮ Almost all optimally coloured complete graphs contain a rainbow Hamilton path ⋮ Graph Tilings in Incompatibility Systems ⋮ A Short proof of the blow-up lemma for approximate decompositions ⋮ Graph and hypergraph colouring via nibble methods: a survey ⋮ A Rainbow Dirac's Theorem ⋮ A rainbow blow-up lemma for almost optimally bounded edge-colourings ⋮ Repeated Patterns in Proper Colorings ⋮ On the number of symbols that forces a transversal

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Rainbow matchings and rainbow connectedness
• Linearly many rainbow trees in properly edge-coloured complete graphs
• Lopsided Lovász Local lemma and Latin transversals
• On a problem of G. Hahn about coloured Hamiltonian paths in \(K_{2n}\)
• Asymptotic behavior of the chromatic index for hypergraphs
• On rainbow trees and cycles
• Solution of the Room square existence problem
• Transversals of latin squares and their generalizations
• An approximate version of a conjecture of Aharoni and Berger
• Rainbow spanning trees in properly coloured complete graphs
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• On a conjecture of Stein
• Multicoloured Hamilton cycles
• Long rainbow cycles and Hamiltonian cycles using many colors in properly edge-colored complete graphs
• Weighted sums of certain dependent random variables
• Concentration of the hypergeometric distribution
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• Concentration Inequalities and Martingale Inequalities: A Survey
• Orthogonal Latin Rectangles
• Hamilton circuits with many colours in properly edge-coloured complete graphs.
• Kotzig Factorizations: Existence and Computational Results
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Decompositions into spanning rainbow structures
• Rainbow matchings in Dirac bipartite graphs
• A counterexample to Stein’s Equi-$n$-square Conjecture
• A Combinatorial Theorem
• A lower bound for the length of a partial transversal in a Latin square
• Multicolored trees in complete graphs
• A lower bound for the length of a partial transversal in a Latin square

This page was built for publication: Rainbow structures in locally bounded colorings of graphs