Properly coloured copies and rainbow copies of large graphs with small maximum degree

DOI10.1002/RSA.20383MaRDI QIDQ2904592zbMATH OpenOpenAlexWikidataFDO

Authors Julia Böttcher, Yoshiharu Kohayakawa, Aldo Procacci

Publication date 14 August 2012

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

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

zbMATH Keywords

Ramsey theoryLovasz local lemmarainbow colouringsproper edge colourings

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Ramsey theory (05D10)

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].

Recommendations

• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• A rainbow blow-up lemma for almost optimally bounded edge-colourings
• Long directed rainbow cycles and rainbow spanning trees

Cites work

• scientific article; zbMATH DE number 1067836 (Why is no real title available?)
• A Combinatorial Theorem
• A property of the colored complete graph
• Alternating Hamiltonian cycles
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Lopsided Lovász Local lemma and Latin transversals
• Multicoloured Hamilton cycles
• On rainbow trees and cycles
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Polychromatic Hamilton cycles
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

Cited in

(19)

• An algorithmic proof of the Lovász local lemma via resampling oracles
• On an anti-Ramsey threshold for random graphs
• Bounded colorings of multipartite graphs and hypergraphs
• 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

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)