Exact values for Ramsey numbers for \(k\)-cycle

For two graphs \( G\) and \( H\), let \( r(G,H)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete graph \( K_m\) are colored in red and blue, then there is either a subgraph isomorphic to \( G\) with all red edges or a subgraph isomorphic to \( H\) with all blue edges. Here we consider the cycle-complete graph Ramsey number, \( r(C_k, K_n)\).

For \( k\) fixed and \( n\) large, the probabilistic method gives

\(\displaystyle r(C_k,K_n) > c (n/\log n)^{(k-1)/(k-2)}. \)

For the upper bound, it is known [1] that for even \( k=2m\), we have

\(\displaystyle r(C_{2m},K_n) \leq c_m (n / \log n)^{m/(m-1)}. \)

For odd \( k=2m+1\), it is known that [2]

\(\displaystyle r(C_{2m+1}, K_n)\leq c_m\frac{n^{1+1/m}}{\log^{1/m}n}. \)

Erdos, Faudree, Rousseau, Schelp [3] proposed the following three problems:


Is it true that for \(n>3\), \begin{equation}r(C_k, K_n) = (k-1)(n-1)+1 \end{equation} if \(k \geq n \)?


What is the smallest value of \(k\) such that \( r(C_k, K_n) = (k-1)(n-1)+1\)?


For a fixed \(n\), what is the minimum value of \(r(C_k,K_n)\) over all \(k\)?

For \( C_{k}\), with \( k>n^2-2\), the result (1) was proven in 1973 by Bondy and Erdos [4]. In 2005, Nikiforov [5] proved (1) also holds for \( k\geq 4n+2\). Moreover, the result has been proven for \( n=3, 4, 5,\) and \( 6\) (with the exception of \( r(C_3, K_3)=6\)) [6][7][8][9][10].

1 Y. Caro, Y. Li, C.C. Rousseau, Y. Zhang. Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers, Discrete Math. 220 (2000) 51-56

2 B. Sudakov. A note on odd cycle-complete graph Ramsey numbers, The Electronic J. of Comb. 9 (2002) N1

3 P. Erdös, R. J. Faudree, C. C. Rousseau and R. H. Schelp, On cycle-complete graph Ramsey numbers, J. Graph Theory 2 (1978), 53-64.

4 J. A. Bondy and P. Erdös, Ramsey numbers for cycles in graphs, J. Comb. Theory Ser. B 14 (1973), 46-54.

5 V. Nikiforov. The cycle-complete graph Ramsey numbers, Combinatorics, Probabliity, & Computing 3 (2005), 349-370.

6 R. J. Faudree and R. H. Schelp. All Ramsey numbers for cycles in graphs, Discrete Math 8 (1974), 313-329.

7 V. Rosta. On a Ramsey type problem of J. A. Bondy and P. Erdös, I & II. J. of Combin. Theory Ser. B 15 (1973), 94-120.

8 Y. J. Sheng, H. Y. Ru, and Z. K. Min. The value of the Ramsey number \( r(C_n, K_4)\) is \( 3(n-1)+1\) (\( n\geq 4\)), Australas. J. Combin 20 (1999), 205-206.

9 B. Bollobás, C.J. Jayawardene, Z. K. Min, C. C. Rousseau, H. Y. Ru, and J. Yang. On a conjecture involving cycle-complete graph Ramsey numbers, Australas. J. Combin 22 (2000), 63-72.

10 I. Schiermeyer. All cycle-complete graph Ramsey numbers \( r(C_m, K_6)\). J. of Graph Theory 44 (2003), 251-260.