广义Ramsey数 p(n,k)的若干性质 (2003年)

设n,k≥3为自然数,p(n,k)是最小的正整数p,使得对任何阶图G,或者G有n点导出子图至少有n-1条边,或者G有k点独立集,则本文证明:(1)p(n,k)≥max{p(n,k-1),p(n-1,k)},(2)当n<3k-4时有p(n,k)≥2k-2+[n/3],这里[·]是最大取整函数。