Ramsey数 r(3,q)中的新下界  

New Lower Bounds of Ramsey Numbers r (3, q)

作　　者：王清贤 王攻本[2] 

机构地区：[1]北京大学计算机科学技术系 [2]北京大学分校

出　　处：《北京大学学报（自然科学版）》1989年第1期117-121,共5页Acta Scientiarum Naturalium Universitatis Pekinensis

摘　　要：我们利用计算机来构造既没有三角形又没有q个顶点的独立集的循环图。当q=14、15、16,17时,由我们构造的循环图得到Ramsey数的四个新下界: r(3,14)≥64; r(3,15)≥73; r(3,16)≥79; r(3,17)≥88。Using a computer, we have constructed four cyclic graphs, None of them contains K3. The first graph has 63 vertices and does not contain K14. The second has 72 vertices and does not contain K15. The third has 78 vertices and does not contain K16. The last has 87 vertices and does not contain K17. Hence we show that r (3, 14)≥64, r(3, 15)≥73, r(3, 16)≥79 and r(3, 17)≥88.

关 键 词：RAMSEY数 RAMSEY图 循环图 

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