An Alternative Proof of the Linearity of the Size-Ramsey Number of Paths
- 2 October 2014
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 24 (3) , 551-555
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.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Partitioning edge-coloured complete graphs into monochromatic cycles and pathsJournal of Combinatorial Theory, Series B, 2014
- Random Graphs2001
- On Size Ramsey Number of Paths, Trees and Circuits. II1990
- Mathematics of Ramsey Theory1990
- Explicit construction of linear sized tolerant networksDiscrete Mathematics, 1988
- Extremal Graph Theory with Emphasis on Probabilistic Methods1986
- On size Ramsey number of paths, trees, and circuits. IJournal of Graph Theory, 1983
- On the combinatorial problems which I would most like to see solvedCombinatorica, 1981
- The size Ramsey numberPeriodica Mathematica Hungarica, 1978