Properly coloured copies and rainbow copies of large graphs with small maximum degree
From MaRDI portal
Publication:2904592
DOI10.1002/RSA.20383zbMATH Open1244.05087arXiv1007.3767OpenAlexW2001344568WikidataQ105583225 ScholiaQ105583225MaRDI QIDQ2904592FDOQ2904592
Authors: Julia Böttcher, Yoshiharu Kohayakawa, Aldo Procacci 
Publication date: 14 August 2012
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
Abstract: Let G be a graph on n vertices with maximum degree D. We use the Lov'asz local lemma to show the following two results about colourings c of the edges of the complete graph K_n. If for each vertex v of K_n the colouring c assigns each colour to at most (n-2)/22.4D^2 edges emanating from v, then there is a copy of G in K_n which is properly edge-coloured by c. This improves on a result of Alon, Jiang, Miller, and Pritikin [Random Struct. Algorithms 23(4), 409-433, 2003]. On the other hand, if c assigns each colour to at most n/51D^2 edges of K_n, then there is a copy of G in K_n such that each edge of G receives a different colour from c. This proves a conjecture of Frieze and Krivelevich [Electron. J. Comb. 15(1), R59, 2008]. Our proofs rely on a framework developed by Lu and Sz'ekely [Electron. J. Comb. 14(1), R63, 2007] for applying the local lemma to random injections. In order to improve the constants in our results we use a version of the local lemma due to Bissacot, Fern'andez, Procacci, and Scoppola [preprint, arXiv:0910.1824].
Full work available at URL: https://arxiv.org/abs/1007.3767
Recommendations
Cites Work
- Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
- Multicoloured Hamilton cycles
- Polychromatic Hamilton cycles
- A Combinatorial Theorem
- On rainbow trees and cycles
- Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
- Lopsided Lovász Local lemma and Latin transversals
- Alternating Hamiltonian cycles
- A property of the colored complete graph
- Graphs with Hamiltonian cycles having adjacent lines different colours
- Title not available (Why is that?)
Cited In (19)
- Bounded colorings of multipartite graphs and hypergraphs
- On an anti-Ramsey threshold for random graphs
- A rainbow blow-up lemma for almost optimally bounded edge-colourings
- Rainbow structures in locally bounded colorings of graphs
- Recent advances on the Hamiltonian problem: survey III
- Commutativity in the Algorithmic Lovász Local Lemma
- Entropy compression versus Lovász local lemma
- A rainbow blow-up lemma for almost optimally bounded edge-colourings
- Improved bounds on coloring of graphs
- Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
- A rainbow Dirac's theorem
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- A rainbow blow-up lemma
- Properly colored Hamilton cycles in Dirac-type hypergraphs
- Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree
- Long directed rainbow cycles and rainbow spanning trees
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- On Hamiltonian Berge cycles in [3]-uniform hypergraphs
- An algorithmic proof of the Lovász local lemma via resampling oracles
This page was built for publication: Properly coloured copies and rainbow copies of large graphs with small maximum degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904592)
