Premium
All cycle‐complete graph Ramsey numbers r ( C m , K 6 )
Author(s) -
Schiermeyer Ingo
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10145
Subject(s) - combinatorics , mathematics , conjecture , independence number , ramsey's theorem , graph , discrete mathematics , complete graph
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