A remark on star-C4 and wheel-C4 Ramsey numbers

Yanbo Zhang (Department of Mathematics, Nanjing University, Nanjing, P.R. China)
Hajo Broersma (Faculty of Electrical Engineering, Mathematics and Computer Science, University of Twente, Enschede, The Netherlands)
Yaojun Chen (Department of Mathematics, Nanjing University, Nanjing, P.R. China)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 2, No 2 (2014): Electronic Journal of Graph Theory and Applications

Given two graphs G1 and G2, the Ramsey number R(G1;G2)is the smallest integer N such that, for any graph G of order N, either G1 is a subgraph of G, or G2 is a subgraph of the complement of G. Let Cn denote a cycle of order n, Wn a wheel of order n+1 and Sn a star of order n. In this paper, it is shown that R(Wn;C4) = R(Sn+1;C4) for n ≥ 6. Based on this result and Parsons' results on R(Sn+1;C4), we establish the best possible general upper bound for R(Wn;C4) and determine some exact values for R(Wn;C4).