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

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

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

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

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

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

** Problem:**

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 \)?

** Problem:**

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

** Problem:**

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].