Ramsey numbers for cycles in graphs (Q2556422): Difference between revisions

For two graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1,G_2)\) is the minimum \(p\) such that for any graph \(G\) of order \(p\), either \(G_1\) is a subgraph of \(G\) of \(G_2\) is a subgraph of the complement \(\bar G\) of \(G\). The authors determine the Ramsey numbers in the cases where \(G_1\) and \(G_2\) are certain cycles. [These Ramsey numbers have since been established completely by \textit{J. Faudree} and \textit{R. H. Schelp} [Discrete Math. 8, 313-329 (1974; Zbl 0294.05122)] and \textit{V. Rosta} [J. Comb. Theory, Ser. B 15, 94-104, 105-120 (1973; Zbl 0261.05118 and Zbl 0261.05119)]. The authors show that \(R(C_n,K_r) \leq nr^2\) for all \(r\) and \(n\) and that \((R(C_n,K_r)=(r-1)(n-1)+1\) if \(n \geq r^2-2\). Let \(K^{t+1}_r\) denote the complete \((t+1)\)-partite graph \(K(r_1, \ldots ,r_{t+1})\) for which \(r_i=r\) for each \(i\). Then \(R(C_n,K^{t+1}_r)=t(n-1)+r\) for sufficiently large \(n\).