Restricted size Ramsey number for P3 versus cycle

Joanna Cyman (Gda\'nsk University of Technology, Department of Technical Physics and Applied Mathematics, Narutowicza 11/12, 80-952 Gda\'nsk, Poland)
Tomasz Dzido (Institute of Informatics, University of Gda\'{n}sk, Wita Stwosza 57, 80-952 Gda\'{n}sk, Poland)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 8, No 2 (2020): Electronic Journal of Graph Theory and Applications

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*(P3,Cn) for 7 ≤ n ≤ 12. We also give new upper bound r*(P3,Cn) ≤ 2n-2 for n ≥ 10 and n is even.