一个实用的检验Kn(3,p)的算法

设Ｋｎ是ｎ个顶点的完全图，若对Ｋｎ的每条边着以红色或蓝色，并且图中既不包含红色团Ｋ３也不包含蓝色团Ｋｐ，这样就得到一个二色边图Ｋｎ，同时将这种染色所得的图记为Ｋｎ（３，ｐ），把使Ｋｎ（３，ｐ）成立的最大值记为Ｒ（３，ｐ），Ｒ（３，ｐ）＝ｒ（３，ｐ）－１，ｒ（３，ｐ）是Ｒａｍｓｅｙ数，本给出一个实用的算法，可以对给定连通图检验Ｋｎ（３，ｐ）是否成立 。

A Practical Algorithm on Verifying Kn(3,p)

Let Kn be the complete graph with order n.If two colors red and blue are assigned to the edges of Kn,and there is neither clique K3 whose edges are all red nor clique Kp whose edges are all blue. so a 2-edge coloring graph Kn has been obtained, such a 2-edge coloring graph is denoted Kn(3,p).The maximum value of n for Kn(3,p) is written as R(3,p),obviously R(3,p)=r(3,p)-1,where r(3,p) is the Ramsey numer. In our works, we give a practical algorithm to verifying Kn(3,p) for a given connected graph.