On vertex Ramsey graphs with forbidden subgraphs

Abstract

A classical vertex Ramsey result due to Nešetřil and Rödl states that given a finite family of graphs $\mathcal{F}$, a graph $A$ and a positive integer $r$, if every graph $B\in \mathcal{F}$ has a $2$-vertex-connected subgraph which is not a subgraph of $A$, then there exists an $\mathcal{F}$-free graph which is vertex $r$-Ramsey with respect to $A$. We prove that this sufficient condition for the existence of an $\mathcal{F}$-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.

arXiv commentOne figure