北京大学学报(自然科学版)

Ramsey数R(K3, Kq-e)

王清贤1, 王攻本2, 阎淑达3   

  1. 1信息工程学院计算机系,郑州,450002;2北京大学分校,北京,100083;3北京大学数学学院,北京,100871
  • 收稿日期:1997-03-25 出版日期:1998-01-20 发布日期:1998-01-20

The Ramsey Numbers R(K3, Kq-e)

WANG Qingxian1, WANG Gongben2, YAN Shuda3   

  1. 1Department of Computer, Information Engineering Institute, Zhengzhou, 450002; 2Branch Campus of Peking University, Beijing, 100083; 3Department of Mathematics, Peking University, Beijing, 100871
  • Received:1997-03-25 Online:1998-01-20 Published:1998-01-20

摘要: 利用一种系统地构造循环着色的算法,借助计算机证明了Ramsey数R(K3,Kq-e) 的下述新下界:
R(K3,K11-e)≥42, R(K3,K13-e)≥54,
R(K3,K14-e)≥59, R(K3,K15-e)≥69。

关键词: Ramsey数, 下界, 循环着色

Abstract: The Ramsey number n=R(G,H) has been defined as the minimum n such that every 2-coloring (red and green) of the edges of the complete graph Kn has a red subgraph G, or a green subgraph H.By constructing cyclic colorings systematically with the help of a microcomputer, it is proved that
R(K3,K11-e)>=42, R(K3,K13-e)>=54,
R(K3,K14-e)>=59, R(K3,K15-e)>=69.

Key words: Ramsey number, lower bound, cyclic coloring

中图分类号: