Degree conditions for Ramsey goodness of paths

Abstract

A classical result of Chvátal implies that if $n\ge (r-1)(t-1)+1$, then any colouring of the edges of $K_n$ in red and blue contains either a monochromatic red $K_r$ or a monochromatic blue $P_t$. We study a natural generalization of his result, determining the exact minimum degree condition for a graph $G$ on $n=(r-1)(t-1)+1$ vertices which guarantees that the same Ramsey property holds in $G$. In particular, using a slight generalization of a result of Haxell, we show that $\delta (G)\ge n-\lceil t/2\rceil$ suffices, and that this bound is best possible. We also use a classical result of Bollobás, Erdős, and Straus to prove a tight minimum degree condition in the case $r=3$ for all $n\ge 2t-1$.

16 pages