Cycle-complete Ramsey numbers (1978)

Originators: P. Erdős, R.J. Faudree, C.C. Rousseau, and R.H. Schelp (presented by Dan Cranston - REGS 2011)

Definitions: For graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the least $n$ such that every red/blue coloring of the edges of the complete graph $K_n$ contains a red copy of $G$ or a blue copy of $H$.

Background: The special case of Ramsey's Theorem for coloring sets of size $2$ implies the $R(G,H)$ is well-defined for all graphs $G$ and $H$. Chvátal [C] proved that $R(T,K_n)=(m-1)(n-1)+1$ whenever $T$ is a tree with $m$ vertices. For the lower bound, the red graph is $(n-1)K_{m-1}$; the upper bound is by induction on $m$ and $n$.

Conjecture 1: ([EFRS]) $R(C_m,K_n)=(m-1)(n-1)+1$ when $m\ge n\ge3$, where $C_m$ is the $m$-vertex cycle, except for the case $(m,n)=(3,3)$.

Comments: The lower bound comes from the same construction as for $R(T,K_n)$. Bondy and Erdős [BE] proved the conjecture when $m\ge n^2-2$. Nikiforov [N] improved this by proving it for $m\ge 4n+2$. The conjecture has also been proved for

$n=3$ (Chartrand-Schuster [CS]; later Rosta [R] and Faudree-Schelp [FS] generalized to all $R(C_m,C_n)$),

$n=4$ (Yang-Huang-Zhang [YHZ]),

$n=5$ (Bollobás et al [BJYHRZ]),

$n=6$ (Schiermeyer [S]), and

$n=7$ (Chen-Cheng-Zhang [CCZ]).

For the next value, $n=8$, the conjecture has been proved when $m=8$ (Jaradat-AlZaleq [JA] and Zhang-Zhang [ZZ]), $m=9$ (Bataineh-Jaradat-AlZaleq [BJA]), and $m\ge 34$ (Nikiforov [N]). The values are larger when $m$ is small, but the formula $R(C_m,K_n)=(m-1)(n-1)+1$ does hold sometimes when $m$ is just slightly less than $n$, such as for $(m,n)\in\{(5,6),(5,7),(6,7),(6,8),(7,8)\}$ (see [R, page 14]).

References:
[BJA] Bataineh, M.S.A.; Jaradat, M.M.M.; Al-Zaleq, L.M.N.; The cycle-complete graph Ramsey number $r(C_9,K_8)$. ISRN Algebra (2011), doi:10.5402/2011/926191.
[BJYHRZ] Bollobás B.; Jayawardene, C.; Yang, J.S.; Huang, Y.R.; Rousseau, C.C.; Zhang, K.M.; On a conjecture involving cycle-complete graph Ramsey numbers. Australas. J. Combin. 22 (2000), 63-71.
[BE] Bondy, J. A.; Erdős, P.; Ramsey numbers for cycles in graphs. J. Combinatorial Theory Ser. B 14 (1973), 46-54.
[CS] Chartrand, G.; Schuster, S.; On the existence of specified cycles in complementary graphs. Bull. Amer. Math. Soc. 77 1971 995-998.
[CCZ] Chen, Y.; Cheng, T.C.E.; Zhang, Y.; The Ramsey numbers $R(C_m,K_7)$ and $R(C_7,K_8)$. European J. Combin. 29 (2008), no. 5, 1337-1352.
[EFRS] Erdős, P.; Faudree, R. J.; Rousseau, C. C.; Schelp, R. H.; On cycle-complete graph Ramsey numbers. J. Graph Theory 2 (1978), no. 1, 53-64.
[FS] Faudree, R. J.; Schelp, R. H.; All Ramsey numbers for cycles in graphs. Discrete Math. 8 (1974), 313-329.
[JA] Jaradat, M. M. M.; Alzaleq, B. M. N.; The cycle-complete graph Ramsey number $r(C_8,K_8)$. SUT J. Math. 43 (2007), no. 1, 85-98.
[N] Nikiforov, V.; The cycle-complete graph Ramsey numbers. Combin. Probab. Comput. 14 (2005), no. 3, 349-370.
[Ra] Radziszowski, R.; Small Ramsey numbers, Revision \#12. Electronic J. Combinatorics, (2009).
[Ro] Rosta, V.; On a Ramsey-type problem of J. A. Bondy and P. Erdős. I, II. J. Combinatorial Theory Ser. B 15 (1973), 94-120.
[S] Schiermeyer, I.; All cycle-complete graph Ramsey numbers $r(C_m,K_6)$. J. Graph Theory 44 (2003), no. 4, 251-260.
[YHZ] Yang, J.S.; Huang, Y.R.; Zhang, K.M.; The value of the Ramsey number $R(C_n,K_4)$ is $3(n-1)+1\ (n\ge4)$. Australas. J. Combin. 20 (1999), 205-206.
[ZZ] Zhang, Y.; Zhang, K.M.; The Ramsey number $R(C_8,K_8)$. Discrete Math. 309 (2009), no. 5, 1084-1090.