The Ramsey numbers R (Cm, K7) and R (C7, K8)

Yaojun Chen; Edwin Tai Chiu Cheng; Yunqing Zhang

doi:10.1016/j.ejc.2007.05.007

The Ramsey numbers R (C_m, K₇) and R (C₇, K₈)

Yaojun Chen, Edwin Tai Chiu Cheng, Yunqing Zhang

Research output: Journal article publication › Journal article › Academic research › peer-review

8 Citations (Scopus)

Abstract

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) = 6 m - 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.

Original language	English
Pages (from-to)	1337-1352
Number of pages	16
Journal	European Journal of Combinatorics
Volume	29
Issue number	5
DOIs	https://doi.org/10.1016/j.ejc.2007.05.007
Publication status	Published - 1 Jul 2008

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics

More information

10.1016/j.ejc.2007.05.007

Cite this

@article{1b246890256041408ffb8ec2e080f0ea,

title = "The Ramsey numbers R (Cm, K7) and R (C7, K8)",

abstract = "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) = 6 m - 5 for m ≥ 7 and R (C7, K8) = 43, with the former result confirming a conjecture due to Erd{\"o}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.",

author = "Yaojun Chen and Cheng, {Edwin Tai Chiu} and Yunqing Zhang",

year = "2008",

month = jul,

day = "1",

doi = "10.1016/j.ejc.2007.05.007",

language = "English",

volume = "29",

pages = "1337--1352",

journal = "European Journal of Combinatorics",

issn = "0195-6698",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

T1 - The Ramsey numbers R (Cm, K7) and R (C7, K8)

AU - Chen, Yaojun

AU - Cheng, Edwin Tai Chiu

AU - Zhang, Yunqing

PY - 2008/7/1

Y1 - 2008/7/1

N2 - 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) = 6 m - 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.

AB - 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) = 6 m - 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.

UR - http://www.scopus.com/inward/record.url?scp=42949096111&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2007.05.007

DO - 10.1016/j.ejc.2007.05.007

M3 - Journal article

VL - 29

SP - 1337

EP - 1352

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

SN - 0195-6698

IS - 5