On the multi-colored Ramsey numbers of paths and even cycles (Q727052)

Summary: In this paper we improve the upper bound on the multi-color Ramsey numbers of paths and even cycles. More precisely, we prove the following. For every \(r\geq 2\) there exists an \(n_0=n_0(r)\) such that for \(n\geq n_0\) we have \[ R_r(P_n) \leq \left(r-\frac{r}{16r^3+1} \right) n. \] For every \(r\geq 2\) and even \(n\) we have \[ R_r(C_n) \leq \left(r-\frac{r}{16r^3+1} \right) n + o(n) \text{ as }n\rightarrow \infty. \] The main tool is a stability version of the Erdős-Gallai theorem that may be of independent interest.