Pn和Ckn的Ramsey数

• 作 者: 裴超平 李雨生
• 机 构: 同济大学数学系,上海,200092
• 出 处: 同济大学学报（自然科学版）
• 发表日期: 2015年9期
• 关键词: Ramsey数 k-幂次图 Ramsey完备性

称Fk为图F的k幂次图,如果V(Fk)=V(F),且Fk中的任意两个顶点相邻当且仅当在F中的距离至多为k.给定图G和H,Ramsey数R(G,H)为最小的正整数N,使得完全图KN的任意红蓝-边着色都会含有一个红色的子图G或者蓝色的子图H.证明了渐近阶R(Pn,Ckn)=(n-1)(x(Ckn)-1)+σ(Ckn)+o(n),其中k是常数.