We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
An Alternative Proof of the Linearity of the Size-Ramsey Number of Paths.
- Authors
DUDEK, ANDRZEJ; PRAŁAT, PAWEŁ
- Abstract
The size-Ramsey number $\^{r} $(F) of a graph F is the smallest integer m such that there exists a graph G on m edges with the property that every colouring of the edges of G with two colours yields a monochromatic copy of F. In 1983, Beck provided a beautiful argument that shows that $\^{r} $(Pn) is linear, solving a problem of Erdős. In this note, we provide another proof of this fact that actually gives a better bound, namely, $\^{r} $(Pn) < 137n for n sufficiently large.
- Subjects
RAMSEY numbers; PATHS &; cycles in graph theory; MONOCHROMATIC light; INTEGERS; LINEAR statistical models
- Publication
Combinatorics, Probability & Computing, 2015, Vol 24, Issue 3, p551
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S096354831400056X