The Ramsey numbers R(Cm, K7) and R(C7, K8)
The Ramsey numbers R(Cm, K7) and R(C7, K8)
复制标题
DOI：
10.1016/j.ejc.2007.05.007
复制
发表时间：
2008-07
期刊：
影响因子：
--
通讯作者：
Yaojun Chen;T. Cheng;Yunqing Zhang
中科院分区：
文献类型：
--
作者：
Yaojun Chen;T. Cheng;Yunqing Zhang
对于给定的两个图G1和G2，Ramsey数R(G1，G2)是最小整数n，使得对任一n阶图G，要么G包含G1，要么G的补包含G2。设Cm表示长为m的圈，KnA是n阶完全图.本文证明了R(Cm，K7)=6m−5对于m≥7，R(C7，K8)=43.前一个结果证实了由ErdöS、Faudree、Rousseau和Schelp提出的猜想：对于m−n−3，R(Cm，Kn)=(m≥1)(n≥1)+1，当n=7时，(m，n)≠(3，3).
For two given graphs G1and G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any graph G of order n, either G contains G1or the complement of G contains G2. Let Cmdenote a cycle of length m and Kna complete graph of order n. In this paper we show that R(Cm,K7)=6m−5 for m≥7 and R(C7,K8)=43, with the former result confirming a conjecture due to Erdös, Faudree, Rousseau and Schelp that R(Cm,Kn)=(m−1)(n−1)+1 for m≥n≥3 and (m,n)≠(3,3) in the case where n=7.