Article ID Journal Published Year Pages File Type
8902963 Discrete Mathematics 2018 9 Pages PDF
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 coloring of the edges of G with two colors, 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=Pn. In particular, we show that 2.00365n≤Rˆ(C≤n,Pn)≤31n. Using similar techniques, we also managed to analyze Rˆ(Cn,Pn), which was investigated before but until last year only by using the regularity method.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,