The Ramsey numbers of paths versus wheels: a complete solution

Abstract

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. We denote by $P_n$ the path on $n$ vertices and $W_m$ the wheel on $m+1$ vertices. Chen et al. and Zhang determined the values of $R(P_n,W_m)$ when $m\le n+1$ and when $n+2\le m\le 2n$, respectively. In this paper we determine all the values of $R(P_n,W_m)$ for the left case $m\ge 2n+1$. Together with Chen et al's and Zhang's results, we give a complete solution to the problem of determining the Ramsey numbers of paths versus wheels.

32 pages, 1 table