若干新的s-偶图的Ramsey数

More results on the s-bipartite Ramsey numbers

一个分部顶点数分别为s和t的完全偶图可用Ks,t来表示.对于正整数s,以及两个偶图G和H,s-偶图Ramsey数BRs(G,H)是一个最小正整数t,使得每一个Ks,t的2-边着色都含有1色的图G或者含有2色的图H.文章提出了一个新的整数线性规划模型来计算两个图的s-偶图Ramsey数.实验结果表明,该模型比以前的模型更加高效.利用该模型,成功地确定了关于s-偶图Ramsey数的55个新的精确值.

Let Ks,t denote the complete bipartite graph with the number of two partitions s and t. For a positive integers and two bipartite graphs G and H, the s-bipartite Ramsey number BRs(G,H) of G and H is the smallest integer t such that every 2-coloring(colors 1 and 2) of the edges of Ks,t contains the a copy of G with color 1 or a copy of H with color 2. In this paper, we propose a new integer linear program(ILP) to compute the s-bipartite Ramsey number for two graphs. In order to show the efficiency of the new ILP, we compare two ILPs on instances for BRs(K3,3,K3,3) in the same hardware and software environment. Experimental results show that the proposed model is much more effective than the previous one. By applying the proposed model, we succeed in deternizning 55 exact values of new s-bipartite Ramsey numbers.