The Ramsey numbers for a cycle of length six or seven versus a clique of order seven

Edwin Tai Chiu Cheng, Yaojun Chen, Yunqing Zhang, Chi To Ng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 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. It was conjectured that R (Cm, Kn) = (m - 1) (n - 1) + 1 for m ≥ n ≥ 3 and (m, n) ≠ (3, 3). We show that R (C6, K7) = 31 and R (C7, K7) = 37, and the latter result confirms the conjecture in the case when m = n = 7.
Original languageEnglish
Pages (from-to)1047-1053
Number of pages7
JournalDiscrete Mathematics
Volume307
Issue number9-10
DOIs
Publication statusPublished - 6 May 2007

Keywords

  • Complete graph
  • Cycle
  • Ramsey number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this