Ramsey numbers of squares of paths
Allen, P.
, Roberts, B. & Skokan, J.
(2015-08-31 - 2015-09-04)
Ramsey numbers of squares of paths
[Paper]. European Conference on Combinatorics, Graph Theory and Applications, Bergen, Norway, NOR.
, Roberts, B. & Skokan, J.
(2015-08-31 - 2015-09-04)
Ramsey numbers of squares of paths
[Paper]. European Conference on Combinatorics, Graph Theory and Applications, Bergen, Norway, NOR.
The Ramsey number R(G;H) has been actively studied for the past 40 years, and it was determined for a large family of pairs (G;H) of graphs. The Ramsey number of paths was determined very early on, but surprisingly very little is known about the Ramsey number for the powers of paths. The r-th power Pr n of a path on n vertices is obtained by joining any two vertices with distance at most r. We determine the exact value of R(P2 n; P2 n) for n large and discuss some related questions.