若干新的s-偶图的Ramsey数  

More results on the s-bipartite Ramsey numbers

作　　者：杨洪 吴璞 邓飞[3] YANG Hong;WU Pu;DENG Fei(School of Information Science and Engineering,Chengdu University,Chengdu 610106,China;Institute of Computing Science and Technology,Guangzhou University,Guangzhou 510006,China;College of Information Science and Technology,Chengdu University of Technology,Chengdu 610059,China)

机构地区：[1]成都大学信息科学与工程学院,四川成都610106 [2]广州大学计算科技研究院,广东广州510006 [3]成都理工大学信息科学与技术学院,四川成都610059

出　　处：《广州大学学报（自然科学版）》2020年第5期1-4,11,共5页Journal of Guangzhou University:Natural Science Edition

基　　金：教育部产学合作协同育人资助项目(202002015045);四川省军民融合战略研究中心资助项目(JMRH-1818);四川省教育厅资助项目(18ZA0118);成都市教育科研教育改革发展专项资助项目(CY2020ZG04)。

摘　　要：一个分部顶点数分别为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.

关 键 词：偶图 RAMSEY数 2-边着色 整数规划模型 

分 类 号：O157.5[理学—数学]