On three-color Ramsey numbers R(C_4, K_(1,m), P_n)

摘要

For given graphs H-1, ... ,H-k, k = 2, the k-color Ramsey number R(H-1, ... ,H-k) is the smallest integer N such that every k-coloring of the edges of a complete graph K-N contains a monochromatic copy of H-i colored in i, for some i with 1 = i = k. Let C-l, K-1,K-m, and P-n denote a cycle of length l, a star of order m + 1 and a path of order n, respectively. In this paper, it is shown that R(C-4, K-1,K-m, P-n) = m + n - 1 + [root m + n - 2] for all m, n = 2 and R(C-4, K-1,K-m, P-n) = m+n-2+[root m + n - 2] if m+n = l(2)+3 and l = 1. Moreover, by discussing the local structure of the polarity graph whose vertices are points in the projective plane over Galois fields, we show that the two upper bounds can be attained for some special m and n. These results also extend some known results on R(C-4, K-1,K-m) obtained by Parsons in 1975 and by Zhang et al. recently. (C) 2018 Elsevier Inc. All rights reserved.