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

DOI10.1002/rsa.20383zbMath1244.05087arXiv1007.3767OpenAlexW2001344568WikidataQ105583225 ScholiaQ105583225MaRDI QIDQ2904592

Julia Böttcher, Aldo Procacci, Yoshiharu Kohayakawa

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

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

Related Items (19)

Commutativity in the Algorithmic Lovász Local Lemma ⋮ Bounded colorings of multipartite graphs and hypergraphs ⋮ On an anti-Ramsey threshold for random graphs ⋮ Long directed rainbow cycles and rainbow spanning trees ⋮ Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree ⋮ Improved bounds on coloring of graphs ⋮ Properly colored Hamilton cycles in Dirac-type hypergraphs ⋮ Moser-Tardos resampling algorithm, entropy compression method and the subset gas ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ A rainbow blow‐up lemma ⋮ Rainbow structures in locally bounded colorings of graphs ⋮ A Rainbow Dirac's Theorem ⋮ Properly colored and rainbow copies of graphs with few cherries ⋮ A rainbow blow-up lemma for almost optimally bounded edge-colourings ⋮ Entropy compression versus Lovász local lemma ⋮ On Hamiltonian Berge cycles in [3-uniform hypergraphs] ⋮ An Algorithmic Proof of the Lovász Local Lemma via Resampling Oracles ⋮ Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas ⋮ Almost spanning subgraphs of random graphs after adversarial edge removal

Cites Work

• Unnamed Item
• Polychromatic Hamilton cycles
• Lopsided Lovász Local lemma and Latin transversals
• On rainbow trees and cycles
• Path and cycle sub-Ramsey numbers and an edge-colouring conjecture
• Alternating Hamiltonian cycles
• A property of the colored complete graph
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Multicoloured Hamilton cycles
• Almost spanning subgraphs of random graphs after adversarial edge removal
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• A Combinatorial Theorem

This page was built for publication: Properly coloured copies and rainbow copies of large graphs with small maximum degree