Three-color Ramsey numbers for paths

For graphs \(G_1,G_2,\dots,G_r\), the Ramsey number \(R(G_1,G_2,\dots,G_r)\) is the smallest positive integer \(n\) such that if the edges of a complete graph \(K_n\) are partitioned into \(r\) disjoint color classes giving \(r\) graphs \(H_1,H_2,\dots,H_r\), then at least one \(H_i(1\leq i\leq r)\) has a subgraph isomorphic to \(G_i\). The existence of such a positive integer is guaranteed by \textit{F. P. Ramsey}'s classical result [Proc. London Math. Soc., 2nd Ser. 30, 264--286 (1930;JFM 55.0032.04)]. The number \(R(G_1,G_2,\dots,G_r)\) is called the Ramsey number for the graphs \(G_1,G_2,\dots,G_r\). In this paper the following theorem conjectured by \textit{R. J. Faudree} and \textit{R. H. Schelp} [Journal of Combinatorial Theory, Ser. B 19, 150--160 (1975; Zbl 0286.05111)] is proved. \noindent Theorem. There exists a positive integer \(n_0\) such that for \(n\geq n_0\) we have \[ R(P_n,P_n,P_n)= \begin{cases} 2n-1 & \text{for odd}\;n\\ 2n-2 & \text{for even}\;n. \end{cases} \]

Recommendations

Cited in

(65)

This page was built for publication: Three-color Ramsey numbers for paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390138)