Size-Ramsey numbers of cycles versus a path

2016/08/23 by Dudek, Andrzej, Khoeini, Farideh, Prałat, Paweł
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1608.06533

Abstract

The size-Ramsey number R(F,H) of a family of graphs F and a graph H is the smallest integer m such that there exists a graph G on m edges with the property that any colouring of the edges of G with two colours, say, red and blue, yields a red copy of a graph from F or a blue copy of H. In this paper we first focus on F = C_{≤ cn}, where C_{≤ cn} is the family of cycles of length at most cn, and H = P_n. In particular, we show that 2.00365 n ≤ R(C_{≤ n},P_n) ≤ 31n. Using similar techniques, we also managed to analyze R(C_n,P_n), which was investigated before but only using the regularity method.

Related

• Note on the multicolour size-Ramsey number for paths
• Two types of size Ramsey numbers for matchings of small order
• On the size-Ramsey number of cycles
• The size-Ramsey number of powers of paths
• On the size Ramsey number of all cycles versus a path