（计算机应用技术专业论文）3色ramsey数r（cm1cm2cm3）.pdf

大连理工大学硕士学位论文 摘要 r a r r t s e y 理论是图论的重要研究内容之一，而3 色r a r n s e y 数理论是其中一个重要的 理论分支，对于3 色r a m s e y 数的确定也是一个重要的研究方向，属于n p 困难问题 r a m s e y 问题在数学的发展中有着重要的理论意义，然而，至今为止，人们仅计算出 部分3 色r a r n s e y 数的值 用r 种颜色对图g 中的所有边进行着色，记着第i 色的边所构成的子图为8 如果 存在一种着色方法使得对于所有的f ( 1 s i ，) 都满足禁止子图e 旺g 。，则称图g 对于 ( q ，4 ，耳) 可，着色r a m s e y 数r ( q ，嘎，皿) 是使得完全图对于( 风，耳) 不可，着色的最小正整数本文所研究的就是当，= 3 且l r , 兰g ( 禁止子图同构于圈) 对 即3 色r a m s e y 数r ( 巴，c o ，) 的相关问题 e r d o s 等人在其研究成果中给出了在, - f l 足够大的情况下r a m s e y 数r ( c ，g ，g ) = 5 肼- 4 和r ( q ，c 4 ，a ) = m + 2 的结论 本文通过数学证明的方法得出了当m 5 时，r ( c 卅，c 3 ，c 3 ) = 5 m 一4 ：在m 1 不是足够 大的情况下，运用临界图概念和有效的分枝限界条件，通过计算机辅助得出当 7 m 。 m ：m a 时r ( c 卅，巳，c o ，) 的所有值，并给出了相应的猜想；为计算r ( 乞，c 4 ，c 4 ) 的值，文中定义了新的临界图概念，并得出结论即当1 1 m 1 9 时r ( c 卅，c 4 ，c 4 ) = m + 2 ， 并在此基础上证明了当m 1 9 ，r ( 巴，c 4 ，c 4 ) = m + 2 成立 关键词：边着色：3 色r a r a s e y 数；临界图：禁止子图；圈 王伟：3 色r a m s e y 数r ( ，c ：，c ) t h r e ec o l o rr a m s e y n u m b e r s 尺( 吒，) a b s t r a c t r a m s e yt h e o r yc o n s t i t u t e st h em a i nr e s e a r c h t z e ao fg r a p ht h e o r y ，a n d3 - c o l o r i n g r a m s e yt h e o r yi sa ni m p o r t a n tb r a n c ho fr a m s e yt h e o r y t h ed e t e r m i n a t i o no f3 - c o l o r i n g r a n ：1 s e yn u m b e ri sa l s oa ni m p o r t a n tr e s e a r c hd i r e c t i o no fr a m s e yt h e o r y ，a n d i ti sm e a n w h i l e an o p o l y n o m i a lp r o b l e m r a m s e yt h e o r yh a sg r e a tt h e o r e t i c a ls i g n i f i c a n c ei nt h ee v o l u t i o n o f m a t h e m a t i c s ，h o w e v e r ，w eo n l yo b t a i n e daf e wo f 3 - c o l o r i n gr a m s e yn u m b e r ss of a r l e t8b et h es u b g m p ho fgw h o s ee d g e sa r eh at h ei t hc o l o ri na nr c o l o r i n go ft h e e d g e so f g i ft h e r ee x i s t sa ，c o l o r i n go ft h ee d g e so fgs u c ht h a tf o r b i d d e ns u b g r a p h e g if o ra l lt 蔓i s r ，t h e ngi ss a i dt ob er c o l o r a b l et o ( h 1 ，h 2 ，e ) t h em u l f i c o l o r r a m s e yn u m b e rr ( q ，马，) i st h es m a l l e s ti n t e g e rns u c ht h a tk i sn o t ，。c o l o r a b l e t o ( 墨，现，珥) t h er a m s e yn u m b e rr ( 巳，吒，c m , ) i ss t u d i e di n t h i sp a p e r ，w h e r e ，= 3 a n d h 兰c e r d 6 sp r o v e d t h a t r ( c ，q ，c 3 ) = 5 m 一4 a n d r ( c 。，c 4 ，c 4 ) = m + 2 w h e n mi ss u f f i c i e n t l y l a r g e t h ep a p e rp r o v e st h a tr ( c 。，c 3 ，c 3 ) = 5 m - 4w h e n 磁5 ；w h e nm li sn o ts u f f i c i e n t l y l a r g ea n d7 巩 m 2 m 3 ，t h i sp a p e ru s e st h ec o n c e p t o f c f i t i c a lg r a p ht oo b t a i na l lt h ev a l u e s o fr a m s e yn u m b e rr ( q ，巴，) ，m e a n w h i l eg i , l e sac o n j e c t u r e a f t e rg i v i n gan e w d e f i n i t i o no f c r i t i c a lg r a p h ，t h i sp a p e ra l s oo b t a i n sa l lt h ev a l u e so f r a m s e yn u m b e r r ( c ，c 4 ， c 4 ) ，w h a ti s r ( 巳，c 4 ，c 4 ) = 研+ 2w h e n1 1 s m 蔓1 9 ，a n da l s op r o v et h a tr ( c m ，c 4 ，c 4 ) = m + 2 w h e n m 1 9 k e yw o r d s ：e d g ec o l o r i n g ；m u l f i c o l o rr a m s e yn u m b e r ；c r i t i c a lg r a p h ；f o r b i d d e n s u b g r a p h ；c y c l e s 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究威果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 日期：丝：! 三! ! 少 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和忙编学位论 文。 作者签名： 斗 导师签名：密立羔 趟年j 兰角! 日 大连理工大学硕士学位论文 引言 若有疗+ 1 只鸽子同时飞进珂个笼子中，则一定有某个笼子中至少飞进两只鸽子，这 就是著名的鸽笼原理，也叫做抽屉原理这个原理十分简单，其正确性也是显而易见的， 但却有十分广泛的应用鸽笼原理的应用在图论和组合论中书中不难找到鸽笼原理有 如下重要的推广： 设g 。，9 2 ，吼，t 是正整数，且吼t ( i = 1 ，2 ，门) ，则存在最小的正整数，( 记作r ( g l ， g ：，吼；r ) ) 使得：对于任意m 元集合s ，若m ，当把s 的所有t t l ；子集放到以个盒子 里时，那么存在某个i ( 1 i n ) 和某吼个元素，它的所有f 元子集都在第i 个盒子里这就 是1 9 3 0 年由r a m s e y 提出并证明了存在性的r a m s e y 定理，并称数，( q 2 ，蟊；f ) 为 r a m s e y 数 当r = 1 时，r a m s e y 定理就是加强形式的鸽笼原理，且容易求出：r ( q 1 ，吼，蟊；1 ) = 吼- n + 1 ，= l 当t = 2 时，用图论术语可把r a m s e y 定理叙述为：对任意正整数吼，g ：，吼，都存 在最小的正整数r ，当m ，时，用n 种颜色对完全图疋，的边任意着色，则一定有某个 单色的子图瓦。( 1 i 疗) 当t = = 2 时，又可如下叙述r a m s e y 定理：设p ，q 是正整数，则存在最小的正整数 r = r ( p ，g ) ( 即r ( p ，g ；2 ) ) ，对任意顶点数大于等于，的图g ，g 中或有p 个顶点的完全子 图，或有g 个顶点的独立集 h a r a r y 等人研究了r a m s e y 数的各种推广形式一种较简单的形式是：设f ，日是图， 定义r ( f ，胃) 是满足下述条件的最小正整数，：用红和蓝两种颜色对r 个顶点完全图x ， 的边任意着色，可以方便地将此定义推广到多个图的情形按此定义，r ( p ，q ) 就是 ，( 巧，e ) 为区分起见，通常称r ( f ，h ) 为广义r a m s e y 数，而称前面定义的r a m s e y 数 为经典r a m s e y 数 r a r n s e y 定理是组合论中一个重要的存在性定理，它的发表推动了组合论等数理科 学的发展，而且关于r a m s e y 定理和r a m s e y 数自身的研究目前已成为组合学中一个重 要的分支即r a m s e y 理论但是，r a m s e y 定理只保证了r a m s e y 数的存在性，并没有给 出计算r a m s e y 数的有效方法目前，确定r a m s e y 数的问题仍然是一个尚未解决的大难 题，要找到一个很小的r a m s e y 数都是很困难的 王伟：3 色r a i n s e y 数r ( c 。，c ：，c ，) e r d 6 s 等人在其研究成果中给出了在m 足够大的情况下r a n - m c y 数r ( q ，g ，c 3 ) = 5 m 一4 和r ( c m ，c 4 ，c 4 ) = 研+ 2 的结论 本文证明了当m 5 时，r ( q ，c 3 ，c 3 ) = 5 m - 4 ；在肌，不是足够大的情况下7 啊 时r ( g ，q ，巳，) 的所有值，并给出了相应的猜想；还定义新的临界图概念，计 算出了r ( q ，c 4 ，c 4 ) 的值，即当1 l 所1 9 时r ( q ，c 4 ，c 4 ) = m + 2 ，并在此基础上证明了 当扰 1 9 ，r ( c 卅，c 4 ，c 4 ) = m + 2 成立 大连理工大学硕士学位论文 1 图的相关知识 r a m s e y 理论是组合数学与图论的主要研究内容之一，3 色r a m s e y 数理论是r a m s e y 理论中一个重要的理论分支。r a m s e y 理论表明：每一种“不规则”的结构，只要它足够 大，就会含有指定大小的“规则”子结构【l j 图论作为- - f - j 历史悠久的学科，吸引着众多学者对其进行研究本文所研究的“3 色r a m s e y 数”是图论领域r a m s e y 问题的一个比较重要的研究方向为了在本文的叙述 及证明过程中避免歧义的产生，有必要先对图论的历史及本文中所涉及到的图论概念进 行一下简单的说明，未说明到的图论概念以图论 2 1 为准 1 1 图论简史 图论本身是应用数学的一部分，因此，历史上图论曾经被好多位数学家各自独立地 建立过关于图论的文字记载最早出现在欧拉1 7 3 6 年的论著中，当时他所考虑的原始问 题有很强的实际背景 图论起源于著名的柯尼斯堡七桥问题在柯尼斯堡的普莱格尔河上有七座桥将河中 的岛与河岸联结起来，问题是要从这四块陆地中任何一块开始，通过每座桥正好一次， 再回到起点然而无数次得尝试都没有成功欧拉在1 7 3 6 年解决了这个问题，他用抽象 分析法将这个问题转化为第一个图论问题：即把每一块陆地用一个点来代替，将每一座 桥用联接相应的两个点的一条线来代替，从而相当于得到一个图，欧拉证明了这个问题 没有解，并且推广了这个问题，给出了对于一个给定的图可以某种方式走遍的判定法则 这项工作使欧拉被公认为图论的创始人 1 8 5 9 年，英国数学家哈密顿发明了一种游戏：用一个正十二面体，它的2 0 个顶点 标出世界著名的2 0 个城市，要求游戏者找一条沿着边通过每个顶点刚好一次的闭回路， 即绕行世界用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成回路 这个问题后来就叫做哈密顿问题由于运筹学、计算机科学和编码理论中的很多问题都 可以转化为哈密顿问题，所以这个问题引起人们广泛的注意和研究 在图论的历史中，还有一个著名的问题四色猜想这个猜想说，如果每个国家 都只由一个单连通域构成，且相邻的两个国家至少有一段公共的边界，则他们在一个平 面或球面上的地球能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色 每个地图可以对应一个图，其中国家对应顶点，国家间的相邻关系对应边所以四色猜 想是图论中的一个问题，它对图的着色理论、平面图理论和代数拓扑图论等分支的发展 起到了推动作用 王伟：3 色r 丑i i l s e y 数尺( c 坩，巳：，c q ) 图论的广泛应用，促进了它自身的发展二十世纪4 0 年代到6 0 年代，拟阵理论、 超图理论、极图理论，以及代数图论、拓扑图论等都有很大的发展二十世纪6 0 年代到 8 0 年代，随着计算机科学的迅速发展和计算机应用的广泛普及，它的发展尤为迅速它 所涉及的领域包括物质结构、电气网络、信息传输、交通运输、城市规划、经济管理和 计算机科学等，几乎包括了人类社会的所有领域图论已经成为人们研究工程、自然科 学甚至社会科学的一个重要工具 1 2 基础知识 1 2 1 图的基本概念 在自然界和人类社会的实际生活中，用图形来描述某些对象或事物之间具有某种特 定关系常常感到特别方便例如：用工艺流程图来描述某项工程中各工序之间的先后关 系：用竞赛图来描述某循环比赛中各选手之间的胜负关系；用网络图来描述某通讯系统 中各通讯站之间信息传递关系；用交通图来描述某地区内各城市之间复杂的铁路连接关 系；用原理电路图来描述某电器内各元件导线连接关系，等等图形中的点表示对象( 如 上例中的工序、选手、通讯站等) ，两点之间的有向或无向连线表示两个对象之间具有 某种特定的关系( 如上例中的先后关系、胜负关系、传递关系、连接关系等) 事实上， 任何一个包含了某种二元关系的系统都可以用图形来模拟由于我们感兴趣的是两个对 象之间是否有某种特定关系，所以图形中两点间连接与否甚为重要，而连接线的蓝直长 短则无关重要，由此通过数学抽象产生图的概念研究图的基本概念和性质、图的理论 及其应用构成了图论的主要内容 本节主要介绍图的基本概念、术语、记号和若干初等结果，这些都是本文最终结论 的基础 ( 1 ) 图 一个图g 定义为一个二元组( g ) ，e ( g ) ) ，可以将其简记作g = ( v ，e ) 二元组中 v ( g ) = v l ，v ：， 表示一个非空的顶点集合，而压( g ) 表示连接顶点与顶点的边集，其 中每一条边仅与其两个端点相关联 ( 2 ) 有限图 顶点集和边集都有限的图称为有限图 本文所涉及的图均为有限简单无向图 ( 3 ) 阶、边数 大连理工大学硕士学位论文 图g = ( v ，e ) 中，任意一条边( “，v ) 可简记“v ；g 顶点的个数称为阶，用p ( g ) = lv ( g ) i 来表示；g 的边数，用q ( g ) = ie ( g ) | 来表示 由以上图的定义可知，一个集合矿和v 上的个二元关系就是一个图因此图的最 本质的内容就是一个二元关系，也就是顶点和边的关联关系如果一个系统或一个结构 具有二元关系，便可以用图作为数学模型来描述它 “) 度 在图g = ( v ，e ) 中，与顶点v ( v v ) 相关联的边的数目，称作是该顶点的度，记作 d ( v ) 顶点度最大的值称为该图g 的最大度，记作a ( g ) = m a x ( d ( v ) ：v v ) ： 顶点度最小的值称为该图g 的最小度，记作占( g ) = m i n d ( v ) ：v v 在有向图g 中，射入一个顶点的边的数目称为该顶点的入度；由一个顶点射出的边 的数目称为该顶点的出度顶点的出度与入度之和就等于该顶点的度数 在任何有向图中，所有顶点的入度之和等于所有顶点的出度之和 每个图中，顶点度数的总和等于边数的两倍，即表示为d ( v ) = 2e ( g ) i 悝r ( g ) ( 5 ) 完全图 在简单图g = ( v ，e ) 中，若每一对顶点问都有边相连，则称该图为完全图；有n 个 顶点的完全图记作e ，其边数为n ( n 一1 ) 2 ( 6 ) 二部图 如果一个图的顶点集合能被分成两个互不相交的集合巧和( 称为部分集) ，且每 条边都将k 中的顶点与砍中的顶点相连，则称此图为二部图，有时也称为二分图或偶图 若k 中的每个顶点与以中的每个顶点都相连接，则称此二部图为完全二部图，记为 其中p t = 吲，p z = 吲 完全掰 1 ) 部图，该图共有且+ 见+ + 办个顶点，这些顶点被分到m 个集合中， 各个集合分别包含a ，p ：，p 。( p i o ) 个顶点，属于同一个集合中的顶点均不相连接，属 于不同集合中的顶点均相互连接完全m 部图可表示为：k p 。 ( 7 ) 子图、禁止子图 设图g = ( 矿，e ) ，如果有图g = ( v ，e ) ，且v 至矿，e e ，则称g 为g 的子图； 若v c v 或e c e ，则称g 为g 的真子图： 若v = v ，e e ，则称g 为g 的生成子图； 若v 匕v ，v “e ，当且仅当v “e 且v ，“矿则称g7 为g 的导出子图： 王伟：3 色r a m s e y 数r ( 巴，巴：，气) 若图日不是图g 的子图，可以称日是g 的一个禁止子图； 将由一组图组成的集合表示为y = g ，g ：，g 。) ，若y 中的图都不是g 的子图， 可以称y 为图g 的一个禁止子图族 ( 8 ) 补图 给定一个图g ，由g 中所有顶点和所有能使g 成为完全图的添加边所组成的图， 际为g 相对于完全图的补图，或简称为图g 的补图，记作g 设图g = ( v ，e ) 是图g = ( 矿，e ) 的子图，若给定另一个图g ”= ( 矿”，e ”) 使得e ”= e e ，且矿”中仅包含三”的边所关联的顶点，则称g ”是子图g 的相对于图g 的补图 ( 9 ) 正则图 若图g 的各顶点的度相同，则称图g 为正则图； 若v v v ( g ) ，d ( v ) = k ，则称图g 为k 一正则图，称它的正则度为缸 ( 1 0 ) 路、圈 在图g = ( y ，d 中，设m ，p 2 ，v v ，由叶u ，v 2 u ，一。组成的边的序列称为连接b 到v 。的路；v ，与v 。分别称作该路的起点和终点，路中边的数目称为路的长度 若一条路中v ，= v 。则这条路称为回路： 若一条路中所有的边均不相同，则称作迹； 若一条路中所有的顶点均不相同，则称作通路或道路，记为：v l v 2 v ( v t v ， 4 ，p o ，q 。，q 2 ，q ，q ，一l 4 ，贝4 ：r ( p o + g o ，q 1 ，q 2 ，q ，- l ；4 ) r ( p o + l ，q l ，q 2 ，吼一1 ；4 ) 一1 】4 r ( q o + 1 ，q l ，吼，外一i ；4 ) 一1 + 1 ( 9 ) 若f = 3 ，5 ，7 ，9 ， ，贝r ( k ，l ；t ) r ( k 一1 ，l ；t ) + r ( k ，f - 1 ；t ) - i ( 1 0 ) 若r = 4 ，6 ，8 ，k ， f ，贝0 r ( k ，；f ) 2 1 7 ( k 一1 ，l ；t ) 一1 ( 1 1 ) 若女，f + 1 4 ，贝4 r ( k ，f ；f ) 2 r ( k - 1 ，l ；t ) - i ( 1 2 ) r ( q o ，g l ，q ，一i ；2 ) 兰r ( q o 一1 ，q l ，q 2 ，q ，1 ；2 ) + r ( q o ，q i 一1 ，q 2 ，q ，一l ；2 ) + r ( q o ，q i ，9 2 ，q ，1 1 ；2 ) 一r + 2 【1 越， 从而有r ( q o + 1 ，q l + 1 ，q ，一i + 1 ) ( q o + q l + + q r 1 ) ! ( g o ! q l ! g ，- 11 ) ； 若，= 2 ，r ( q o ，q 1 ) r ( q o 一1 ，9 1 ) + r ( g o ，g i 1 ) ； 若r ( q 。一1 ，q 1 ) 与r ( q o ，q 一1 ) 均为偶数，则：r ( q o ，q 1 ) r ( q o - 1 ，q i ) + r ( q o ，q i 一1 ) 一l ( 1 3 叫) k 斗3 1 ( 1 4 ) r ( q o ，弘。q h ；1 ) = q ，一r + 1 若r = 2 ，受r ( q o ，q l ；1 ) = 口o + 可1 一1 ( 1 5 ) r ( k ，z ；2 ) ( 七一1 ) ( ，一1 ) + 1 t 1 4 1 ( 1 6 ) 5 = m i n k ， ，n r ( k ，) 2 m c 1 5 】 ( 1 7 ) 如果j 3 ，则2 2 r ( s ，j ) 咖 2 v 2 【1 5 j ( 1 8 ) 对任意j 3 ，e ( 3 ，s ) ( s 2 + 3 ) 2 ( 1 9 ) g ( k ；2 ) = k ：r ( 1 ，g ) = 1 ；r ( 2 ，g ) = i 矿( g ) i ( 2 0 ) r ，+ ；( 肌) ( r ，( 所) 一1 ) ( 皿( 肌) 一1 ) + 1 ( 2 1 ) r ( q o ，g l ，吼1 ) ( r ( q o ，吼) 一1 ) ( 尺( 吼+ l ，吼一1 ) 一1 ) + 1 ( 2 2 ) r ( q o ，叮l ，q r - 1 ) ( q o + 1 ) ( 月( 吼一q o + 1 ，q 2 ，吼，甄一1 ) 一1 ) + 1 _ 在推导r a m s e y 数的下界公式、改进已有的上下界结果的证明过程中经常使用这些 性质在计算机的辅助下，利用有关性质求取r a m s e y 数的具体值时，可以有效的改善 程序的性能，节省计算的时间 1 5 王伟：3 胁a a s e 数r ( c 卅l ，c ：，c ) 2 3 2r a m s e y 数的相关结论 r a m s e y 问题是“图论”研究领域的难题之一，求解r a m s e y 数也相当困难，至今只 求出几个r a m s e y 数以及几十个r a m s e y 的上下界在这里，简单地将这些r a m s e y 数或 其上下界列举出来 ( 1 ) 2 色r a m s e s y 数 当t = 2 ，r = 2 时，经典r a m s e y 数r ( k ，) 的概念提出后，e r d 6 s 和s z e k e r e s 就对经 典r a m s e y 数给出了一个简单的界：r ( k ，) f 七：_ 2 1 l 彤一l 根据前面提及的性质1 和性质2 ，可以知道r a m s e y 数有如下性质：r ( k ，d = r ( t ，k ) ， r ( q 。，2 ) = r ( 2 ，q 。) = q 。，所以在这里只需要考虑3 ，k 的情况到本文成稿之曰，已经 完全确定的r a m s e y 数只有l o 个除了r ( 3 ，3 ) = 6 之外，g r e e n w o o d 和g l e a s o n n 于1 9 5 5 年在历史上首次计算出r a m s e y 数的精确值，得到：r ( 3 ，4 ) = 9 ，r ( 3 ，5 ) = 1 4 ，r ( 4 ，4 ) = 1 8 ， r ( 3 ，3 ，3 ) = 1 7 除了这些值之外，对其他r a m s e y 数的研究就显得越来越困难，计算量也越来越巨 大即使借助当时最先进的计算机进行科学计算也要耗费大量的运算时间虽然对于 r a m s e y 数研究的困难与日俱增，但仍然硕果累累，近年来计算出来的结果 1 】有：r ( 3 ，6 ) = 1 8 ；r ( 3 ，7 ) = 2 3 ：r ( 3 ，9 ) = 3 6 ；r ( a ，8 ) = 2 8 ；r ( 4 ，5 ) = 2 5 表2 1 列出了到2 0 0 4 年7 月份为止当3 k 1 0 ，3 ，1 5 时r ( k ，) 的已知值和最好 的上下界表2 2 中列出了一些较大数值的r a m s e y 数的下界，即r ( k ，) r 【l o 】 ( 2 ) 多色r a m s e y 数 在广义r a m s e y 定理中，当着色数， 2 时，称其为多色r a m s e y 数对于多色r a m s e y 数的研究是r a m s e y 理论一个重要的研究课题，研究过程主要是从顶点较少的规则图形 起始，逐渐向顶点较多的不规则图形发展这使得确定多色r a m s e y 数的工作越来越复 杂，也越来越具有困难，对计算多色r a m s e y 数的算法要求也越来越高就目前所能提 供的硬件条件和理论水平而言，也只是主要集中在圈、完全图等有限的几个规则图形及 其相关图的研究上关于这几种图形，现有的研究成果得到的也只是该方向上部分 r a m s e y 数的精确值和界限，下面给出现今已有的一些结论 多色经典r a m s e y 数 g r e e n w o o d 和g l e a s o n 证明了结论r 3 ( 3 ) = r ( 3 ，3 ，3 ) = r ( 3 ，3 ，3 ；2 ) = 1 7 【 k a l b f l e i s c h 和s t a n t o n 证明了k i ；的2 色临界r a m s e y 数的相关结论【1 4 ，1 鄹 大连理工大学硕士学位论文 表2 1r a m s e y 数r ( k ，z ) ( 3 s k 1 0 ，3 ，1 5 ) t a b 2 1 r a m s e y n u m b e r s r ( k ，d ( 3 k 1 0 ，3 ，1 5 ) 表2 2 较大的r a m s e y 数r ( k ，) 的下界 t a b 2 2l o w e rb o u n d sf o rh i g h e rr a m s e yn u m b e r sr ( k ，) h e i n r i c h 证明了墨5 的2 色r a m s c y 数的相关结论“6 】 p i w a k o w s k i 和r a d z i s z o w s k i 证明了k i 。的1 1 5 色着色 g r e e n w o o d 和g l e a s o n 在其论文中给出了一个广泛的上界：r ( k a ，墨) 2 - r + r ( 岛，曩一，置一1 ，砖+ 。，k r ) i = 1 1 7 王伟：3 色r a m s e y 数r ( c 。，巴，气) 表2 3 多色r a m s e y 数足( m ) 的下界 t a b 2 3l o w e rb o u n d sf o rd i a g o n a lm u l t i c o l o rr a m s e yn u m b e r s 足( 啪) 在表2 3 中只列举出一些已发表的r ，( m ) 精确值，仍有一些b ( m ) 的下界未列举在其 中，为了文章的完整性，列举如下： m a t h o n 证明了3 2 1 l r 3 ( 7 ) 嘲 x u x i a o d o n g 和x i e z h e n g 证明了2 7 2 1 r 4 ( 5 ) l 2 0 1 x u x i a o d o n g 和x i e z h e n g 证明了2 6 0 8 2 兰兄( 5 ) 1 但被最多人研究且最具吸引力的结论是：5 1 r ( 3 ) = g ( 3 ，3 ，3 ，3 ) 6 2 ，其下界于1 9 7 3 年由c h u n g 2 1 1 证明，而上界于2 0 0 4 年由f e r e s ，k r a m e r ，r a d z i s z o w s k i 证明 表2 43 色r a m s e y 数r ( 3 ，k ，m ) 的下界 t a b 2 4 l o w e r b o u n d s f o r d i a g o n a l3 - c o l o r r a m s e y n u m b e r s r ( 3 ，k ，m ) 4 色r a m s e y 数 当r = 4 时，称其为4 色r a m s e y 数 对于4 色r a m s e y 数的研究成果知道以下结论： e x o o 证明了9 3 r ( 3 ，3 ，3 ，4 ) 1 5 3 x ux i a o d o n g 和x i ez h e n 证明了1 6 2 c m ( 2 m 一3 ) 2 9 b ( p q + 1 ) ( 耳( p + 1 ) 一1 ) ( b ( g + 1 ) 一1 ) 当p - q 时，耳( p g + 1 ) 耳( p + 1 ) ( 耳( g + 1 ) 一1 ) 。0 1 r ( p , q l + 1 ，p ，q ，+ 1 ) ( r ( a + 1 ，p ，+ 1 ) 一1 ) ( r ( 吼+ 1 ，q ，+ 1 ) 一1 ) 耳+ 。( m ) ( r ，) 一1 ) ( r ( r a ) 一1 ) r ( 毛，k 2 ，t ) ( r ( 毛，砖) 一1 ) ( r ( t + 1 ，一) 一1 ) p “ r ( k 。，k 2 ，k ，) ( 墨+ 1 ) ( r ( 女2 一i + l ，屯，i ) 一1 ) u “ 2 4 本文的工作 本文所研究的具体内容大致可以分为以下3 个部分： 王伟：3r h m e y r ( c ，巴：，吒) e r d # s 等a z 9r a m s e y 数r ( q ，c 3 ，g ) 给出了如下结论：在聊足够大的情况下， r ( 巴，c 3 ，c 3 ) = 5 m 一4 本文第三章就对m 5 的情况进行了研究，证明了当m 5 时 r ( q ，c 3 ，c 3 ) = 5 m 一4 e r d 6 s 等人对于r a m s e y 数足( q ，c c ) 给出了如下结果：当竹 m 2 m 3 且聊l 足 够大的情况下r ( c o 矿q ，q ，) 的值本文第四章就对玛不是足够大的情况下进行了研 究，给出了当7 m 。 m 2 m 3 且( 玛，m 2 ) ( 3 ，3 ) 时r a m s e y 数r ( g ，c 卅，) 的所有值 e r d 6 s 等人对于r a m s e y 数r ( c o ，c 4 ，c 4 ) 给出了如下结论：在m 足够大的情况下 r ( 巳，c 4 ，c 4 ) = m + 2 本文第五章的内容就是对坍- 5 的情况进行了研究，给出了新的临 界图的定义，确定了当肌5 时r ( q ，c 4 ，c 4 ) 的精确值，并且确定了当m 1 1 时，r ( q ， c 4 ，g ) = m + 2 大连理工大学硕士学位论文 3r a m s e y 数r ( 厶，c 3 ，c 3 ) 3 1 基本引理 本章主要研究了3 色r a m s e y 数r ( c 卅，c - , ，c 卅t ) 当m ：= 3 且= 3 即r ( c m ，c 3 ，c 3 ) 的 值对于3 色r a m s e y 数r ( c ：，c 3 ，c 3 ) 的研究成果，己知如下： g r e e n w o o d 和g l e a s o n 证明了：玛( c 3 ) = 1 7 e x o o 和r e y n o l d s 等人证明了：尺( c 4 ，g ，c 3 ) = 1 7 e r d 6 s 等人【3 2 1 给出了引理3 1 ： 引理3 1 r ( c 。，c j ，c j ) 5 m 一4 ， ( 3 1 a ) r ( q ，c 2 ，c ： + 1 ) 4 脚一3 ，其中，2 ，k 1 ， ( 3 1 6 ) r ( q ，c 2 f c ：“1 ) 2 ( m + ，) 一3 ， ( 3 1 c ) r ( g ，c ：f ，c 矗) m + k + ，一2 ( 3 1 d ) 且当m 足够大时，等号成立 3 2r a m s e y 数r ( c 名，g ，g ) = 5 m - 4 本章主要对e r d 6 s 等人证明的引理( 3 1 x z ) 进行了讨论和研究，即：当m 足够大时， r ( c 卅，c 3 ，c 3 ) = 5 m - 4 通过数学证明得出r ( 巴，c 3 ，c 3 ) 的下界和上界，并由此综合得出 了关于丑( c 。，c 3 ，c 3 ) 的新结论：当m 5 时，r ( g ，c 3 ，c 3 ) = 5 m 一4 在本章及随后章节的讨论中会涉及到关于图的因子分解对图g 的一种着色方式 就是对图g 因子分解的一种形象化表示，所以在这里给出因子分解的概念 定义3 1 图g 的因子分解 一个图g 的一个因子是g 的一个非完全不连通的生成子图如果g 是这些因子的 边不相交的并，称g 是这些因子6 的和这样的一个并，称其为g 的一个因子分解 3 2 1 尺( g ，c 3 ，g ) 下界的确定 引理3 2 r ( c ：，c 3 ，c 3 ) 5 m 一4 证明：下面给出一种对k 5 ( ) 所有边进行3 着色的方法令e = h w ) 。“5 ；o j 4 ， 1 曼i 2 ) 即e = y o l ：i ，v iv 2 ，v 2 码，屿v 4 ，v 4 1 ，0 且e = v o v 2 ，v 1 y 3 ，v 2 p 4 ，v 3 v 5 ，y 4 v 1 ，则得到 e u e = e ( k s ) 并且嘏) n e = g ，同时由每个f , 0 f 2 ) 导出的k 5 的因子同构于c 5 王伟：3 色r 矗m s e y 数胄( c 埘，c ：，已，) 下面将把蚝扩展成为恐。 首先，定义矿( 憋，1 ) = v j