摘要:Ramsey数R(G,H)为最小的正整数N，使得对完全图KN的边集的任意红蓝二着色，都存在红色的子图G或者蓝色的子图H.结合Burr的一个定理和图的分割原理，证明当n≥|G|2+2χ(G)α(G)时，R(Pn,G)=(χ(G)－1)(n－1)+σ(G).

摘要:称 ~$F^k$~ 为图~$F$ ~的~$k$-幂次图，如果~$V(F^k)=V(F)$~, 且~$F^k$~中的任意两个顶点相邻当且仅当他们在~$F$~中的距离至多为~$k$。 给定图~$G$~和~$H$，~Ramsey~数~$R(G,H)$~为最小的正整数~$N$，使得完全图~$K_N$~的任意红蓝-边着色都会含有一个红色的子图~$G$~或者蓝色的子图~$H$。Pokrovskiy~证明了~$R(P_n,P_n^k)=(n-1)k lfloor frac{n}{k 1}rfloor$，解决了~Allen~等人在~2010~年提出的一个猜想。本文证明渐近阶~$R(P_n,C_n^k)=(n-1)(chi(C_n^k)-1) sigma(C_n^k) o(n)$, 其中~$k$~是常数。