试论3色ramsey数r（c,m,1，c,m,2，c,m,3）

《试论3色ramsey数r（c,m,1，c,m,2，c,m,3）》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学硕士学位论文3色Ramsey数R（C<,m<,1>>，C<,m<,2>>，C<,m<,3>>）姓名：王伟申请学位级别：硕士专业：计算机应用技术指导教师：杨元生20051201大连理工大学硕士学位论文摘要Rarrtsey理论是图论的重要研究内容之一，而3色Rarnsey数理论是其中一个重要的理论分支，对于3色Ramsey数的确定也是一个重要的研究方向，属于NP困难问题．Ramsey问题在数学的发展中有着重要的理论意义，然而，至今为止，人们仅计算出～部分3色Rarnsey数的值．用r种颜色对图G中的所有边进行着色，记着第i色的边所构成的子图为8

2、．如果存在一种着色方法使得对于所有的f(1si≤，)都满足禁止子图E旺G。，则称图G对于(q，4，．．，耳)可，着色．Ramsey数R(q，嘎，．，皿)是使得完全图％对于(风，％，．．．，耳)不可，着色的最小正整数．本文所研究的就是当，=3且Lr,兰G(禁止子图同构于圈)对即3色Ramsey数R(巴．，co，，％)的相关问题．Erdos等人在其研究成果中给出了在／,-fl足够大的情况下Ramsey数R(C，G，G)=5肼-4和R(q，c4，a)=m+2的结论．本文通过数学证明的方法得出了当m≥5时，R(c卅，C3，c3)=5m一4：在m1不是足够大的情

3、况下，运用临界图概念和有效的分枝限界条件，通过计算机辅助得出当7≥m。>m：≥ma时R(c卅，，巳，，co，)的所有值，并给出了相应的猜想；为计算R(乞，c4，c4)的值，文中定义了新的临界图概念，并得出结论即当11≤m≤19时R(c卅，c4，C4)=m+2，并在此基础上证明了当m>19，R(巴，c4，c4)=m+2成立．关键词：边着色：3色Rarasey数；临界图：禁止子图；圈王伟：3色Ramsey数R(‘，C：，c∞)ThreeColorRamseyNumbers尺(吒，％，％)AbstractRamseytheoryconstitutesthem

4、ainresearch{tzeaofgraphtheory，and3-coloringRamseytheoryisanimportantbranchofRamseytheory．thedeterminationof3-coloringRan：1seynumberisalsoanimportantresearchdirectionofRamseytheory，anditismeanwhileaNo—PolynomialProblem．Ramseytheoryhasgreattheoreticalsignificanceintheevolutionofma

5、thematics，however，weonlyobtainedafewof3-coloringRamseynumbersSOfar．Let8bethesubgmphofGwhoseedgesarehathei—thcolorinanr—coloringoftheedgesofG．Ifthereexistsa，·coloringoftheedgesofGsuchthatforbiddensubgraphE≤GIforallt蔓isr，thenGissaidtober—colorableto(H1，H2，¨．，E)．ThemulficolorRamsey

6、numberR(q，马，．，Ⅳ，)isthesmallestintegernsuchthatKisnot，。colorableto(墨，现，．，珥)．TheRamseynumberR(巳．，吒，Cm,)isstudiedinthispaper，where，=3andH兰C．Erd6sprovedthatR(C．，q，c3)=5m一4andR(c。，c4，c4)=m+2whenmissufficientlylarge．ThepaperprovesthatR(c。，C3，C3)=5m-4when磁≥5；Whenmlisnotsufficientlylarg

7、eand7≥巩>m2≥m3，thispaperusestheconceptofcfiticalgraphtoobtainallthevaluesofRamseynumberR(q，，％，巴，)，meanwhilegi,lesaconjecture．Aftergivinganewdefinitionofcriticalgraph，thispaperalsoobtainsallthevaluesofRamseynumberR(C．，c4，c4)，whatisR(巳，C4，c4)=研+2when11sm蔓19，andalsoprovethatR(Cm，c4，

8、c4)=m+2whenm>19．KeyWords：EdgeColoring；Mulficolo