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

Yaojun Chen, Edwin Tai Chiu Cheng, Yunqing Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)1337-1352
Number of pages16
JournalEuropean Journal of Combinatorics
Volume29
Issue number5
DOIs
Publication statusPublished - 1 Jul 2008

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Cite this