On size Ramsey number of paths, trees, and circuits. I
- 1 March 1983
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 7 (1) , 115-129
- https://doi.org/10.1002/jgt.3190070115
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 ř(Pn) of the path Pn 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.Keywords
This publication has 5 references indexed in Scilit:
- On the combinatorial problems which I would most like to see solvedCombinatorica, 1981
- The size Ramsey numberPeriodica Mathematica Hungarica, 1978
- Asymptotic lower bounds for Ramsey functionsDiscrete Mathematics, 1977
- Hamiltonian circuits in random graphsDiscrete Mathematics, 1976
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952