Restricted size Ramsey number for P3 versus cycle

Abstract

Let F, G and H be simple graphs. We say F → (G,H) if for every 2-coloring of the edges of F there exists a red copy of G or a blue copy of H in F. The Ramsey number r(G,H) is defined as r(G,H) = min{|V(F)|: F → (G,H)}, while the restricted size Ramsey number r^*(G,H) is defined as r^*(G,H) = min{|E(F)|: F → (G,H),|V(F)| = r(G,H)}. In this paper we determine previously unknown restricted size Ramsey numbers r^*(P₃,C_n) for 7 ≤ n ≤ 12. We also give new upper bound r^*(P₃,C_n) ≤ 2n-2 for n ≥ 10 and n is even.