圈与K4的临界完全图Ramsey数

摘要

对给定的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个点的圈.