Problem #613: Let $n\geq 3$ and $G$ be a graph with...

---

Progress

Faudree proved that this is true if $G$ has $2n+1$ vertices (this appears to be unpublished, but is referred to e.g. in [Er93]).

In other words, if $\mathcal{F}$ is the family of all odd cycles and $K_{1,n}$ is the star with $n+1$ vertices then this problem asks whether\[\widehat{r}(K_{1,n},\mathcal{F})=\binom{2n+1}{2}-\binom{n}{2},\]where $\widehat{r}$ is the size Ramsey number.

This is false, as disproved by Pikhurko [Pi01], who proved the bounds\[n^2+0.577 n^{3/2}<\widehat{r}(K_{1,n},\mathcal{F})< n^2+\sqrt{2}n^{3/2}+n\]for all large $n$.

In fact this conjectured bound already fails for $n=5$, as noted by Pikhurko. This disproof for $n=5$ has been formalised by Tao (see the comments).

See also the entry in the graphs problem collection.