All cycle‐complete graph Ramsey numbers r ( C m , K 6 )

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