On vertex Ramsey graphs with forbidden subgraphs

DOI10.1016/J.DISC.2023.113806MaRDI QIDQ6177416zbMATH OpenFDO

Authors Sahar Diskin, Ilay Hoshen, Michael Krivelevich, M. E. Zhukovskii

Publication date 17 January 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphsvertex Ramsey

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80) Ramsey theory (05D10) Combinatorial probability (60C05)

Abstract: A classical vertex Ramsey result due to Nev{s}etv{r}il and R"odl states that given a finite family of graphs $mathcalF$, a graph $A$ and a positive integer $r$, if every graph $BinmathcalF$ has a $2$-vertex-connected subgraph which is not a subgraph of $A$, then there exists an $mathcalF$-free graph which is vertex $r$-Ramsey with respect to $A$. We prove that this sufficient condition for the existence of an $mathcalF$-free graph which is vertex $r$-Ramsey with respect to $A$ is also necessary for large enough number of colours $r$. We further show a generalisation of the result to a family of graphs and the typical existence of such a subgraph in a dense binomial random graph.

Recommendations

• Vertex Ramsey properties of families of graphs
• Ramsey families which exclude a graph
• Vertex Ramsey properties of randomly perturbed graphs
• The Ramsey Property for Families of Graphs Which Exclude a Given Graph
• Minimal vertex Ramsey graphs and minimal forbidden subgraphs

Cites work

• A note on generalized chromatic number and generalized girth
• Bounding Ramsey numbers through large deviation inequalities
• Graphs without large triangle free subgraphs
• scientific article; zbMATH DE number 426364 (Why is no real title available?)
• scientific article; zbMATH DE number 3536154 (Why is no real title available?)
• On \(K_s\)-free subgraphs in \(K_{s+k}\)-free graphs and vertex Folkman numbers
• On generalized Ramsey numbers of Erdős and Rogers
• Ramsey families which exclude a graph
• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• The Construction of Certain Graphs
• The Ramsey Property for Families of Graphs Which Exclude a Given Graph

Cited in

(1)

• Indivisibility for classes of graphs

This page was built for publication: On vertex Ramsey graphs with forbidden subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6177416)