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

doi:10.1016/j.disc.2006.07.036

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 publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	1047-1053
Number of pages	7
Journal	Discrete Mathematics
Volume	307
Issue number	9-10
DOIs	https://doi.org/10.1016/j.disc.2006.07.036
Publication status	Published - 6 May 2007

Keywords

Complete graph
Cycle
Ramsey number

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

More information

10.1016/j.disc.2006.07.036

Cite this

@article{b7af209c78a34ecc933e2ead3555b8a6,

title = "The Ramsey numbers for a cycle of length six or seven versus a clique of order seven",

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.",

keywords = "Complete graph, Cycle, Ramsey number",

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

year = "2007",

month = may,

day = "6",

doi = "10.1016/j.disc.2006.07.036",

language = "English",

volume = "307",

pages = "1047--1053",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "9-10",

}

TY - JOUR

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

AU - Cheng, Edwin Tai Chiu

AU - Chen, Yaojun

AU - Zhang, Yunqing

AU - Ng, Chi To

PY - 2007/5/6

Y1 - 2007/5/6

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. 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.

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. 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.

KW - Complete graph

KW - Cycle

KW - Ramsey number

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

U2 - 10.1016/j.disc.2006.07.036

DO - 10.1016/j.disc.2006.07.036

M3 - Journal article

VL - 307

SP - 1047

EP - 1053

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 9-10

ER -