The cycle-complete graph Ramsey numbers. (English) Zbl 1071.05051

The cycle-complete graph Ramsey number \(r(C_p, K_r)\) is defined as the smallest integer \(n\) such that every graph \(G\) of order \(n\) contains a cycle \(C_p\) or has independence number \(\alpha (G) \geq r\). It has been conjectured by P. Erdős, R. J. Faudree, C. C. Rousseau and R. H. Schelp [J. Graph Theory 2, 53–64 (1978; Zbl 0383.05027)] that \(r(C_p, K_r) = (p - 1) (r - 1) + 1\) for all \(p \geq r \geq 3\) (except \(r(C_3, K_3) = 6\)). In the present paper it is proved that the conjecture holds for all \(r\geq3\) and \(p\geq 4r+2\).


05C55 Generalized Ramsey theory


Zbl 0383.05027
Full Text: DOI arXiv