On size Ramsey number of paths, trees, and circuits. I

Abstract

Abstract The size Ramsey number ř ( G ) of a graph G is the smallest integer ř such that there is a graph F of ř edges with the property that any two‐coloring of the edges of F yields a monochromatic copy of G . First we show that the size Ramsey number ř( P n ) of the path P n of length n is linear in n , solving a problem of Erdös. Second we present a general upper bound on size Ramsey numbers of trees.