Premium
On size Ramsey number of paths, trees, and circuits. I
Author(s) -
Beck JóZsef
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070115
Subject(s) - ramsey's theorem , combinatorics , mathematics , monochromatic color , graph , integer (computer science) , upper and lower bounds , discrete mathematics , computer science , mathematical analysis , botany , biology , programming language
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.