导　　师： 杨元生

学科专业： H1203

授予学位： 硕士

作　　者： ;

机构地区： 大连理工大学

摘　　要： 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成立.

关 键 词： 边着色 色 数 临界图 禁止子图 图论

分 类 号： [O157.6 TP301.6]

领　　域： [理学] [理学] [自动化与计算机技术] [自动化与计算机技术]