All cycle-complete graph Ramsey numbers r(Cm, K6)

✍ Scribed by Ingo Schiermeyer

• Publisher: John Wiley and Sons
• Year: 2003
• Tongue: English
• Weight: 122 KB
• Volume: 44
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.10145

✦ Synopsis

Abstract

The cycle‐complete graph Ramsey number r(C~m~, K~n~) is the smallest integer N such that every graph G of order N contains a cycle C~m~ on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erdős, Faudree, Rousseau and Schelp that r(C~m~, K~n~) = (__m −1) (n − 1) + 1 for all m ≥ n ≥ 3 (except r(C~3~, K~3~) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n^2^ − 2__n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003