用图的分割原理计算一些Ramsey数

Using Partitioning Graphs to Calculate Some Ramsey Numbers

摘要:

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

Abstract:

Ramsey number is the smallest integer N such that for any redblue edgecoloring of KN, there is a red subgraph G or a blue subgraph H. In this paper, we use a theorem of Burr and the method of partitioning graphs to prove that if n≥|G|2+2χ(G)α(G), then R(Pn,G)=(χ(G)－1)(n－1)+σ(G).