关于小数n的若干3-色Ramsey数R（C₄，4_4，,K_1,n）

Some 3-Color Ramsey Numbers R（C₄，4_4，,K_1,n） for Small n

摘要: 对于给定的图G₁，G₂，···，G_k，k≥2，k-色Ramsey数R（G₁，G₂，···，G_k）是最小的正整数p。使得对p阶完全图进行任意的k-边着色，总是存在某个着i色的单色图G_i ，其中1≤i≤k。设 C ₄是长度为4的圈，K _1,n是n+1阶的星。张雪梅等证明：对任意n有R（C₄，4_4，,K_1,n）≤n+⌈4√4n+5⌉+3，并且给出该上界可达的某n。本文借助计算机构造极值图，确定了四个新的3-色Ramsey数，即n=7,8,9,10时R（C₄，4_4，,K_1,n）的确切值，尤其当n=7时，该值恰好也达到了上面的上界。

Abstract: For k given graphs G₁，G₂，···，G_k，k≥2, the k-color Ramsey number, denoted by R（G₁，G₂，···，G_k）, is the smallest integer p such that if we arbitrarily color the edges of a complete graph of order p with k colors, then it always contains a monochromatic copy of G_i colored with i, for some 1≤i≤k. Let C ₄ be a cycle of length 4 and K _1,n a star of order n+1. Zhang et al.  show that R（C₄，4_4，,K_1,n）≤n+⌈4√4n+5⌉+3 for all n and the upper bound can be attained for some n. In this paper, making use of a computer to construct some extremal graphs, we will determine some new values of three-color Ramsey numbers R（C₄，4_4，,K_1,n） for n=7,8,9,10, especially when n=7 the above general upper bound is attained again.