圈与K4的临界完全图Ramsey数

Complete Critical Ramsey Numbers of Cycle and K4 Numbers

摘要:

对给定的2个图G和H，Ramsey数r(G,H)是最小的正整数r，使得对完全图Kr的边任意红蓝着色或存在红色子图G、或存在蓝色子图H.临界完全图Ramsey数rK(G,H)是最大的正整数n，使得图Kr－Kn的边任意红蓝着色或存在红色子图G或存在蓝色子图H.当正整数n≥5时，rK(Cn,K4)=n/2，Cn为n个点的圈.

Abstract:

For graphs G and H, Ramsey number r(G,H) is the smallest integer r such that every red/blue edge coloring of Kr contains either a red copy of G, or a blue copy of H. Complete critical Ramsey number rK(G,H) is the largest integer n such that every 2-coloring of Kr－Kn contains either a red copy of G, or a blue copy of H. When positive integer n≥5, rK(Cn,K4)=n/2, Cn is cycle with n vertices.