3色Ramsey数R(C,C,C)

来源 :大连理工大学 | 被引量 : 0次 | 上传用户:jiangyongan
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Ramsey理论是图论的重要研究内容之一,而3色Ramsey数理论是其中一个重要的理论分支,对于3色Ramsey数的确定也是一个重要的研究方向,属于NP困难问题.Ramsey问题在数学的发展中有着重要的理论意义,然而,至今为止,人们仅计算出一部分3色Ramsey数的值. 用r种颜色对图G中的所有边进行着色,记着第i色的边所构成的子图为Gi.如果存在一种着色方法使得对于所有的i(1≤i≤r)都满足禁止子图Hi()Gi,则称图G对于(H1,H2,…,Hr)可r着色.Ramsey数R(H1,H2,…,Hr)是使得完全图Kn对于(H1,H2,…,Hr)不可r着色的最小正整数.本文所研究的就是当r=3且Hi≌Cm(禁止子图同构于圈)时即3色Ramsey数R(Cm1,Cm2,Cm3)的相关问题. Erdos等人在其研究成果中给出了在m足够大的情况下Ramsey数R(Cm,C3,C3)=5m-4和R(Cm,C4,C4)=m+2的结论. 本文通过数学证明的方法得出了当m≥5时,R(Cm,C3,C3)=5m-4;在M1不是足够大的情况下,运用临界图概念和有效的分枝限界条件,通过计算机辅助得出当7≥m1>m2≥M3时R(Cm1,Cm2,Cm3)的所有值,并给出了相应的猜想;为计算R(Cm,C4,C4)的值,文中定义了新的临界图概念,并得出结论即当11≤m≤19时R(Cm,C4,C4)=m+2,并在此基础上证明了当m>19,R(Cm,C4,C4)=m+2成立.
其他文献
期刊
期刊
会议
期刊
期刊
期刊
期刊
期刊
会议
学位