The cycle-complete graph Ramsey number r ( C 8 , K 8 )

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 independent 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 ). In this paper we will present a proof for the conjecture in the case n = m = 8 .