Portal de Periódicos da CAPES

A note on the size Ramsey numbers for matchings versus cycles

2020; Institute of Mathematics of the Czech Academy of Sciences; Volume: 146; Issue: 2 Linguagem: Inglês

10.21136/mb.2020.0174-18

2464-7136

Edy Tri Baskoro, Tomáš Vetrík,

Advanced Graph Theory Research

For graphs G, F 1 , F 2 , we write G → (F 1 , F 2 ) if for every red-blue colouring of the edge set of G we have a red copy of F 1 or a blue copy of F 2 in G.The size Ramsey number r(F 1 , F 2 ) is the minimum number of edges of a graph G such that G → (F 1 , F 2 ).Erdős and Faudree proved that for the cycle Cn of length n and for t 2 matchings tK 2 , the size Ramsey number r(tK 2 , Cn) < n + (4t + 3) √ n.We improve their upper bound for t = 2 and t = 3 by showing that r(2K 2 , Cn) n + 2 √ 3n + 9 for n 12 and r(3K 2 , Cn) < n + 6 √ n + 9 for n 25.