On the Ramsey property of families of graphs

Abstract:

For graphs $A$ and $B$ the relation $A \to (B)_r^1$ means that for every $r$-coloring of the vertices of $A$ there is a monochromatic copy of $B$ in $A$. $\operatorname {Forb} ({G_1},{G_2}, \ldots ,{G_n})$ is the family of graphs which do not embed any one of the graphs ${G_1},{G_2}, \ldots ,{G_n}$, a family $\mathcal {F}$ of graphs has the Ramsey property if for every graph $B \in \mathcal {F}$ there is a graph $A \in \mathcal {F}$ such that $A \to (B)_r^1$. Nešetřil and Rödl (1976) have proven that if either both graphs $G$ and $K$ are two-connected or the complements of both graphs $G$ and $K$ are two-connected then $\operatorname {Forb} (G,K)$ has the Ramsey property. We prove that if $\overline G$ is disconnected and $K$ is disconnected then $\operatorname {Forb} (G,K)$ does not have the Ramsey property, except for four pairs of graphs $(G,K)$. A family $\mathcal {F}$ of finite graphs is an age if there is a countable graph $G$ whose set of finite induced subgraphs is $\mathcal {F}$. We characterize those pairs of graphs $(G,H)$ for which $\operatorname {Forb} (G,H)$ is not an age but has the Ramsey property.