Properly colored and rainbow copies of graphs with few cherries

DOI10.1016/j.endm.2015.06.043zbMath1346.05184arXiv1504.06176OpenAlexW1710336405WikidataQ56226594 ScholiaQ56226594MaRDI QIDQ5890911

Jan Volec, Benjamin Sudakov

Publication date: 14 October 2016

Published in: Electronic Notes in Discrete Mathematics, Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

spanning subgraphslocal lemmarainbow and properly colored subgraphsRamsey-type problemsproperly colored subgraphsrainbow subgraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Ramsey theory (05D10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Bounded colorings of multipartite graphs and hypergraphs, Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles, Properly colored cycles of different lengths in edge-colored complete graphs, Long directed rainbow cycles and rainbow spanning trees, Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree, A rainbow blow‐up lemma, A Rainbow Dirac's Theorem, Linearly many rainbow trees in properly edge-coloured complete graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lopsided Lovász Local lemma and Latin transversals
• Using Lovász local lemma in the space of random injections
• 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
• Properly coloured Hamiltonian cycles in edge-coloured complete graphs
• Graphs with Hamiltonian cycles having adjacent lines different colours
• Polychromatic cliques
• Multicoloured Hamilton cycles
• Multicolored subsets in colored hypergraphs
• Properly coloured copies and rainbow copies of large graphs with small maximum degree
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• A Combinatorial Theorem
• Graph colouring and the probabilistic method