On three-color Ramsey number of paths

Abstract

Let $G_1,G_2,...,G_t$ be graphs. The multicolor Ramsey number $R(G_1,G_2,...,G_t)$ is the smallest positive integer $n$ such that if the edges of complete graph $K_n$ are partitioned into $t$ disjoint color classes giving $t$ graphs $H_1,H_2,...,H_t$, then at least one $H_i$ has a subgraph isomorphic to $G_i$. In this paper, we prove that if $(n,m)\ne (3,3),(3,4)$ and $m\ge n$, then $R(P_3,P_n,P_m)=R(P_n,P_m)=m+\lfloor \frac{n}{2}\rfloor -1$. Consequently $R(P_3,m{K}_2,n{K}_2)=2m+n-1$ for $m\ge n\ge 3$.