The cycle-complete graph Ramsey number r(C6,K8)≤38

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 show that r ( C 6 , K 8 ) ≤ 38 .