（运筹学与控制论专业论文）几类图的均匀染色.pdf

山东大学硕士学位论文 中文摘要 本论文所考虑的图均为简单的有限的无向图设g 是一个图，我们 用y ( g ) ，i g i ，e ( g ) ，e ( g ) ，( g ) ，6 ( g ) 和9 ( g ) 分别表示g 的项点集合， 阶( 顶点数) ，边集合，边数，最大度，最小度和围长在4 i 引起混淆的情况 下，( g ) ，6 ( g ) 和g ( a ) 可分别简记为，6 和夕图g 的一个k 一顶点染色， 是指k 种颜色l ，2 ，k 对于g 的各个顶点的一个分配；如果任意两个相邻 顶点都分配到不同的颜色，称染色是正常的设咖是图g 的一个正常的顶 点染色，若砂的任何两种不同颜色所染的顶点数r j 至多相差l ，称是g 的 一个均匀染色如果咖是网g 的一个均匀七一顶点染色，称是g 的一个 均匀惫一染色图g 可进行均匀奄一染色的最小整数k 称为g 的均匀色数 ，记为x 。( g ) w m e y e r 在f 1 1 中证明了任意树丁都存在均匀( 挈 + 1 ) 一染色，e g g l e t o n 后来改进了w m e y e r 证明过程，并证明了树t 对于任意整数k a ( t ) 2 1 + 1 ，都存在均匀惫一染色w m e y e r 基于其证明结果提出了以下均匀染色猜想 ( e c c ) ： 猜想1 ：对于任意一个既不是完全图也不是奇圈的连通图g ，有x e ( c ) ( g ) h a j n a l 和s z e m e r 6 d i 【2 1 2 证明了：任意图g ，对于任意的整数k a c g ) + i ， 都存在均匀k 一染色 c h e a ，l i h 和w u 4 】证明了：如果图g 是一个连通图，且既不是完全图，奇 圈又不是完全二部图k 2 m + l 2 。+ 1 ，( g ) = 掣，那么g 存在均匀a 一染 色基于这一结果，c h e n ，l i h 和w u 提出了以下e a c c 猜想，可以算是e c c 的改进形式： 猜想2 ：如果g 是一个连通图，且既不是完全图，奇圈又不是完全二部 图心机+ i ，2 m + 1 ，( g ) = a ，那么g 存在均匀一染色 从这个猜想我们可以认为，它等价于尬( g ) a ，它的结果包含了e c c 的结论如果说e c c 是正确的，那么e a c c 就足关于非正则图的结论 c h e a 和l i h 5 1 证明了： ( 1 ) t 是一棵树，如果t 3 5 ( t ) 一8 ，或者t = 3 a ( t ) 一l o ，那么t 存在均 匀3 一染色； i 山东大学硕士学位论文 ( 2 ) t = t ( x y ) 是一棵非空的树，如果1 i x i - l r l i 1 ，那么对所有的k 2 , t 存在均匀k 一染色； ( 3 ) 如果ij xj l y i i 1 ，那么丁存在均匀k 一染色当且仅当 k2m a x 3 ，( i t i + 1 ) ( a ( t 一) + 2 ) ) ，其中t ，是t 的任意一个最大度 点 b i h 和w u 6 1 证明了：如果图g 是一个连通的非完伞的二部图，那么 有x e ( g ) sa c c ) ；完全二部图k n ，。存在均匀七一染色当且仅当f n l k 2 j 1 一 【n lr k l 2 jsl ；图a ( x ，y ) 是一个具有e 条边的连通的二部图，若l x l = m 他= 1 1 厂i ，e 【m m + 1 ) j ( m 一礼) + 2 m ，那么有x e ( a ) f m ( n + 1 ) 1 + 1 h p y a p 和y z h a n g 在【7 】中证明了：如果图g 是一个连通的外平面 图，a 3 ，那么图g 存在均匀一染色； y z h a n g ，h p y a p 在1 1 0 l 中证明了以下定理：任意平面图g ，a ( g ) 1 3 ， 对任意整数m z x ( a ) ，都存在均匀m 一染色 本论文主要讨论了均匀染色的背景，并且证明了以下的主要结果： 1 最大度8 ，围长g 5 的平面图g 存在均匀一染色 2 最大度a 5 ，围长夕1 2 的平面图g 存在均匀一染色 3 设g 是一个不含4 ，5 圈的平面图，9 ，那么g 存在均匀一染色 4 一些图类的平方图的均匀染色的讨论 5 一些图类的m y c i e l s k i 图的均匀染色 关键词：均匀染色；均匀染色数；平面图；围长；平方图 i i 山东大学硕士学位论文 a b s t r a c t a l lg r a p h sc o n s i d e r e di nt h i sp a p e ra r ef i n i t e ，s i m p l e ，a n du n d i r e c t e d f o r ag r a p hg ，w eu s ey ( g ) ， g | ，丹( g ) ，e ( g ) ，( g ) ，似g ) a n d 口( g ) t od e n o t e t h ev e r t e xs e t ，o r d e r ，e d g es e t ，s i z e ，m a x i m u md e g r e e ，m m i m u md e g r e e ，a n d g i r t h ，r e s p e c t i v e l y f o rav e r t e xv y ( g ) ，l e t ) d e n o t e st h en e i g h b o ro f v e r t e xt ，a n d 如( 移) = i n a ( t ，) i i fu y ( g ) ，c l u jd e n o t e st h es u b g r a p ho f gi n d u c e db yu f o rav e r t e xu y ( g ) ，g 一让d e n o t e st h es u b g i r a p ho fg b yd e l e t i n gt h ev e r t e x “t o g e t h e rw i t hi t si n c i d e n te d g e s f o ra ne ( 1 9 ez 剪， g x yd e n o t e st h es u b g r a p ho fgb yd e l e t i n gt h ee d g ex y f o rucv ( g 1 a n dwcy ( g ) ，e ( u ，w ) d e n o t e st h en u m b e ro fe d g e sb e t w e e nua n dw e ( u ，w ) d e n o t e se ( u 】，w ) t h ec o m p l e t eb i p a r t i t eg r a p hw i t hb i p a r t i t i o n ( x ，y ) ，w h e r ei x i = ma n dl y f = 礼，i sd e n o t e db yk m s o m e t i m e s ，w e d e n o t e ( g ) ，6 ( g ) ，9 ( g ) ，( z g ( u ) ，g ( ) a s ，6 ，g ，c f ( u ) ，人，( ，t ) i ns i m p l e a p r o p e rk - c o l o r i n go fag r a p hgi sam a p p i n g f r o mv ( a ) t o l ，2 ，后) s u c ht h a t 咖( z ) 咖( 钞) f o re v e r ye d g ex yo fg ap r o p e rv e r t e xc o l o r i n g i se q u i t a b l ei ft h es i z eo fc o l o rc l a s s e sd i f f e rb ya tm o s to n e t h ee q u i t a b l e c h r o m a t i cn u m b e ro fgi sd e n o t e db yx c ( g ) t h ee q u i t a b l ec h r o m a t i ct h r e s h o l d o fg ，d e n o t e db y ( g ) ，i st h es m a l l e s ti n t e g e rms u c ht h a tgi se q u i t a b l y 伽 c o l o r a b l ef o ra l l 馆m i ti so b v i o u st h a t ( g ) 砭( g ) f o ra n yg r a p hg h a j n a la n ds z e m e r 6 d i 【2 】p r o v e dt h a tx ：( g ) ( g ) + 1f o re a c hg r a p hg t h i s a n s w e r e daq u e s t i o no fp a u le r d s s m e y e r 【1 】p r o v e dt h a tx + ( t ) 垒笋1 + l f o ra n yt r e eta n dh em a d et h ef o l l o w i n gc o n j e c t u r e c o r o e c t u r e1f o ra n yc o n n e c t e dg r a p hg ，e x c e p tk na n d 伤m + lf o ra l l m 1 ， x 。( g ) s ( g ) r e c e n t l y , c h e r t ，l i ha n dw uf 4 1 4p u tf o r t ht h ef o l l o w i n gc o n j e c t u r e c o n j e c t u r e2 f o ra n yc o n n e c t e dg r a p hg ，e x c e p tk n ，q m + 1a n d k 2 m + 1 2 m + 1f o ra l lm 1 ， 砭( g ) s ( g ) i 【i 山东大学硕士学位论文 t h ec o n j e c t u r ei sp r o v e dt ob et r u ef o rg r a p h sgs a t i s f y i n g ( g ) 粤 o ra ( c ) 3 ，b i p a r t i t eg r a p h sf 6 1 6 ，p l a n a rg r a p h sw i t ha21 3 【1 0 1a n d o u t e r p l a n a rg r a p h s 【7 1 r e c e n t l y , w ua n dw a n g 【1 5 jd i s c u a s e dt h ee q u i t a b l e c o l o r i n go fp l a n a rg r a p h sw i t hl a r g eg i r t h i nt h i sp a p e r ，w es h a l lp r o v eb yu s i n gt h es i m i l a rm c t h o di n 【1 0 1t h a t c o n j e c t u r e2i st r u ef o rp l a n a rg r a p h sg ( i ) i f 8a n dg 5 ，o r ( i i ) 5 a n dg 1 2 ，o r ( i i i ) w i t h o u4 , 5 一c y c l e s a n dm a k es o m ed i s s c u s so fs q u a r eg r a p h s a n dm y c i e l s k ig r a p h sa b o u te q u i t a b l ec o l o r i n g k e yw o r d s ：e q u i t a b l ec o l o r i n g ，e q u i t a b l ec h r o m a t i cn u m b e r ，p l a n a r g r a p h s ，g i r t h ，s q u a r eg r a p h s i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均己在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 自主! 厄 e l 、l ， 二 期：卫。夕f 叶 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅：本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：超导师签名：逊日期：型：兰：笙 山东大学硕士学位论文 第一章综述 图论尚未萨式建立的时候，染色问题已经提出并有广泛的研究和发展了 如今染色已是图论中相当重要且具有活力的一个领域了在这里我们讨论的 是一种特定的局限性的染色问题：顶点染色，通俗的说就是，如果我们可以通 过给网络模型的结点染色来给代理人分配资源，那么现在我们关心的是，如何 尽可能平均的分配资源网络模型一般都是建立在图的基础上图g ( v ，e ) 是由点集合v ( g ) 和边的集合e ( g ) 四色猜想是图论染色问题上最著名的问题四色猜想是英国青年学 生f r a n c i sg u t h r i e 在1 8 5 2 年提出来的，当他给英国地图染色时发现4 种颜 色是必要的于是向他的哥哥f r e d e r i c kg u t h r i e 提出出如下猜想： 任何地图上的国家只需要4 种颜色来染，使得任何具有共同边界 的两个国家颜色都不相同 f r e d e r i c k 证明不了。转而请教他的老师一当时伦敦大学教授数学家a d em o r g a n 这位教授也无法证明，就写信给爱尔兰的数学家w r h a m i l t o n h a m i l t o n 同样也无法证明起初这个问题并没有引起数学家的重视，认为是 一个不证即明的事实但经过一些尝试之后，发现并不是那么回事1 8 7 8 年， 伦敦数学会负责人a c a y l e y 向伦敦数学会成员正式宣布了这一问题于是形 成当今著名的四色猜想 设g 是一个图，没有重边和环的图叫做简单图除非特别指出，本文研究 的图均指有限简单无向图对于图g 中的顶点“和 ，若边e = u e ( g ) ， 则称钇和1 相邻，札和t ，互为邻点；称和f ，是p 的端点， 和f ，分别与p 关 联若g 的边e 和厂有一个公共端点，则称e 和厂相邻在图g 中与顶点u 相邻的顶点的全体叫作u 的邻域，记作( u ) 称g m ) 为顶点u 的度 数，记作如( u ) 称度数为k 的顶点为“点我们用y ( g ) ，l v l ，e ( g ) ，e ( g ) ， ( g ) ，6 ( g ) 和g ( c ) 分别表示g 的项点集合，阶( 顶点数) ，边集合，边数，最 l 山东大学硕士学位论文 大度，最小度和围长在不引起混淆的情况下，hc a ) ，6 ( g ) 和( g ) 可分别简 记为，d 和g 对于图g = ( ue ) 和图h = ( v ：e ，) ，若有v ke e ，则称图h 是 图g 的一个子图对于v y ( g ) ，我们把图g 中属于v 的顶点以及与v 中的点关联的边都删除所得到的图记作a v 或g v7 对于v 7 y ( g ) ， 我们把由v 作为顶点集，e 7 = e l e = u u e ( g ) ，i t ，u v 7 ) 作为边集的图 叫做g 中由顶点子集v 7 导出的子图，记作a v ，】 图g 的途径是一个有限非空的点边交替序列u = ? j o e l 铆e 2 e k u ，使得 对1 i 1 ，那么t 存在均匀七一染色当且仅当k2m a x ( 3 ， 可粤赫杀 ) ，其中t ，是丁的任意一个最大度点 l i h 和w u 6 l 证明了：对一个连通的非完全的二部图g ，有x 。( g ) s ( g ) ； 完全二部图，。存在均匀惫一染色当且仪当f n k 2 j 一【n lp k l 2 j l ； 图c ( x ：y ) 是一个具有e 条边的连通的二部图，若i x l = 7 1 t i i , = i y l ， ( h + 3 ：) 广( t - - 一1 ) ，由引理1 3 ，a 中存在不相邻的两点口，它们同时相邻于嵋中 的一点，y ，且只相邻于嵋中的，y 点 令g 。= g ( v t 7 ) u 口，p ) ) u 吲，g 2 = g ( a q ，p ) ) u ，y ) 】 显然有e ( g 2 ) e ( g ( a 】) + 一2 ；+ t + 一警e ( g 2 ) ，矛盾 子情况3 2 对任意点“，屹u ，有p ( ，w ) 1 一1 在这种情况下有e ( u k ，w ) 2 t 令l = uku t ) ，由( 1 ) 有 e ( l ：) ( a 一4 ) t + 2 t + 1 因此有e ( g 2 l ) 坠掣，由引理1 3 ，l 中存在不相邻的两 点口，p ，同时相邻于中的一点7 ，且只相邻中的7 点 令g a = g 2 f ( 7 t o q ，p ) 】，g 4 = g 2 f ( l q ，p ) u 7 e l i 上面的讨论有e ( g 4 ) e ( g 2 ) + 一2 a t + 2 t + a 一警( 2 ( a 一2 ) 一 3 ) t m a x z 土一3 ，) g 4 存在均匀( 一2 ) 一染色因此g 2 存在均匀( a 一1 ) - 染色，g 存在均匀一染色 若n a t ，不妨假设n = a ( t + 1 ) 一歹，其中0 j ，对礼用归纳法 由引理1 - l ，g 存在一个度数至多是3 的点t 1 由归纳假设，平面图g u 存 在均匀一染色咖，设其颜色类为h ，仫，其中i k l = 或t + 1 ，i = 1 ， 8 山东大学硕士学位论文 2 ，因为d ( u ) 3 ，我们假设( u ) uv 2u 如果存在某i 4 有i k l = t ，那么把u 加入k ，将得到g 的一个均匀一染色因此，对于 所有的i 4 有ik i = + 1 若n = a ( 1 + 1 ) 一1 ，则在g 中添加一悬挂点， 此点与g 的任意一个非最大度点相邻；若住= ( + 1 ) 一2 ，则在g 中添加 路v l 忱地，其中t ，l 是g 的任意一个非最大度点设这样得到的新的平面图 为g ，那么i g l = a ( t + 1 ) ，g ( c ) 5 ，由前部分证明可知g 存在均匀一 染色，那么g 也存在均匀一染色 口 定理2 6 最大度a 之5 ，围长g 1 2 的平面图g 存在均匀一染色 证明：我们首先考虑 ，= a t 的情况因为g 是平面图，且9 1 2 ， 所以g 存在一条边z 秒，其中d ( z ) s2 显然只需考虑x ，y 的情况 设吖= ： ，( z ) c h u 假设存在叫使得e ( 伽：吖) = 0 由( 1 ) ， ( 2 ) 有e ( uk ，w u w ) 2 ( a - - 2 ) t ，其中嵋= k 伽，因此有2 ( 一2 ) + 1 e ( g ) g ( n 一2 ) = - 2 ( a t 一2 ) 因为a 5 ，这是不可能的因此对于 任意点w k 有e ，吖) 21 由( 1 ) 有e ( u 蜣，吖) 2 ( 一2 ) 显然 i = 3 有e ( uk u t z ) ，w ) a ( t 一1 ) 因此有( 一1 ) + 1 ( 一1 ) ，这样t 6 t = 3 令a = u u z ，由引理l 。3 ，a 中存在不相邻的两点n ，p ，它们同时相邻 于w 中的一点7 ，且只相邻于w 中的，y 点 令g t = g 【( 吖 7 ) u ( n ，) ) 】，g 2 = g ( a q ，p ) ) u 7 ) 】，有e ( g 2 ) e ( g ) 一 e ( a ，w ) + a 一2 + + 一警( 一2 ) t 由引理1 3 ，( 南存在均 匀( 一1 ) 一染色，因此g 存在均匀一染色 若n a t ，不妨假设佗= ( t + 1 ) 一j ，其中0 1 1 山东大学硕士学位论文 坠掣，由引理1 3 ，a 中存在不相邻的两点o ，p ，它们同时相邻于w 中 的一点7 ，r p , 相邻于吖中的7 点 令g l = g ( 吖( 一y ) u n ，) ) u 屹】，g 2 = g 【( a f n ，) ) un ) 显然有e ( c 2 ) e ( g m 】) + 一2 ( 5 一古) + 一普( a - 3 ) t 根据五色定 理，平面图g 2 是5 - 可染色的，因此有x ( c 2 ) 坠譬擎生，由引理1 3 ，中存在不相邻的两点n ，它们同时 相邻于嵋中的一点，y ，且只相邻嵋中的，y 点 令g x = g 【( w 7 u 口，p ) ) 】，g 2 = g 【( 八【a ，p ，) u - r 1 通过上面的讨论有e ( g 2 ) e ( g 【，】) + 一2 可1 0 + t + a 一鲁 现对e ( c 2 ) 用归纳法来证明g 2 存在均匀( a 一1 ) 一染色由引理2 1 ，g 2 中存在一条边t r y ，其中d ( 仳) 3 由归纳假设，g 2 一t r y 存在一个均 匀( 一1 ) - 染色仍设其颜色类为m ，k ，玩一1 ，其中i m l = t ，i = 1 ， ，一1 现假设让， m ，n ( u ) c y , u k u k 令= m u ，由( 1 ) 有， e ( um ，) ( a 一4 ) t i - - - - - 4 子情况3 1 存在点y 2 圪，使得e ( y a ，w ) = 0 1 令圪= 砼【耽 ，由( 1 ) ，( 2 ) 有e ( uk ，w u 巧) 2 ( 一4 ) ， i - - - - - 4 一1 假设存在点y a k ，使得e ( 蜘，w ) = 0 由( 3 ) 有，e ( uk ，k 舶) ) ( 一4 ) t t 否则，对于圪中的任意一点y 有e ( 可，巧) i ，这样e ( 蚝，圪) 因此有 e ( g 2 ) 之2 ( 一4 ) t + t + 1 西l o + t + a 一普e ( g 2 ) ，矛盾 1 2 山东大学硕士学位论文 子情况3 2 对任意点w k u y s ，有e ( w ? ) 1 一1 在这种情况下有e ( y 2 u v 3 ：w ) 2 t 令l = uku 缸 ，由( 1 ) 有 i - - - - - 2 e ( l w ) ( a 一4 ) f + 2 + 1 因此有e ( g 2 【l 】) s e ( g 2 ) 一e ( l ，w ) s ( 3 一 击) + a 一普i l l = ( 一2 ) + 1 ( a + 3 2 ) ( t - - 1 ) r ，由引理1 3 ，l 中存在不相 邻的两点n ，同时相邻于w 中的一点，y ，且只相邻中的7 点 令g 3 = g 2 【( w 【7 ) u a ，) l ，g 4 = g 2 ( ( 队 a ，p ) u ，y ) 】由上面的讨论有 e ( g 4 ) e ( g 2 l ) + a - 2 _ ( 3 - 击a ) t + 2 a - 百1 0 8 ( 2 ( 一2 ) 一3 ) 一m a x 一3 ：) 由引理1 4 ，g 4 存在均匀( a 一2 ) - 染色因此g 2 存在均匀( a i ) - 染色， g 存在均匀一染色 若n a t ，不妨设礼= a ( t + 1 ) 一歹，其中0 j 分别染色0 ，2 ，3 ，1 ，2 ，即完成染色对于n 三2 ( m o d4 ) 前n - 6 个顶点按前 面的方法处理，对最后6 个顶点x ，y z ，1 1 ，v ，w ( 编号为1 3 , 5 ，n ) 分别染 色0 ，2 ，3 ，1 ，2 ，3 ，即完成染色对于n 三3 ( r o o d4 ) 前1 1 7 个顶点按前面的 方法处理，对于最后的7 个顶点( 编号为n - 6 ，n ) 分别染色0 ，2 ，3 ，1 ，0 ， 2 ，3 ，即完成了染色容易得到一卜边的染色都是均匀的所以均匀- 染色猜想 对于圈c 。m 6 ) 的平方图成立 定理4 ，3 圈c 。( n 6 ) 的平方图是均匀缸可染色的 4 3 树的平方图 对于直径为1 的树t 的平方图是它本身，均匀直径为2 的树t 是星，其 平方图是k 。，都是均匀( 铲) + 1 可染色的对于直径为3 的树t ，仅有两个 顶点的度刁i 为1 ，设这两个点为z ，y ，并且这两个顶点到任意的顶点的距离小 于等于2 ，则图( p ) = i g i 一1 选一个与x 关联的度为l 的顶点，“和选一 个与秒关联的度为l 的顶点1 2 札，u 染相同颜色，其余的顶点各染一种颜色，故 得到一个均匀i g i 一1 一染色所以均匀a ( t 2 ) 一可染色对于直径为4 的树t ， 有且仅有一个点与其他任意的顶点的距离小于等于2 ，故有( p ) = i g i 1 ，而 直径两端的树n 。距离大于2 ，故可以得到一个均匀( 严) 染色 定理4 4 直径为1 ，2 的树t 的平方图是均匀a ( t 2 ) + 1 - 可染色的；直径 为3 ，4 的树t 的平方图是均匀( 铲) 可染色的 引理4 5 最大度为( 丁) 的树的平方图是( 砷退化的 证树t 至少有1 个度为1 的顶点不妨设为z ，那么z 在t 的平方图罩的 度依赖于z 的邻点y ，值为y 在树t 中的度，最大为，对于树t 的平方图 的子图，皆有树t 的子图生成，所以必存在度为1 的顶点，即在平方图中的有 顶点的度不超过( 丁) ，所以总是存在度不超过( t ) 的顶点，所以说最大 度为a ( t ) 的树的平方图是( t ) 退化的 1 5 山东大学硕士学位论文 引理4 6 ( 1 3 】a 2 7 d ，k ( d + + 1 ) 2 那么所有的d 退化的最大度不 超过的图是均匀七一染色的 定理4 7 当树丁的最大度( n 和其平方图俨的最大度a ( t 2 ) 满足下 面的不等式： a ( t 2 ) 1 4 ( 7 1 ) + 1 ， 那么树t 的平方图就是均匀a ( t 2 ) 可染色的 证由引理4 5 知道，最大度为a ( t ) 的树的平方图是( 丁) - 退化的根据 引理4 6 的条件，可证 对于其他情况比较复杂，需进一步的讨论 1 6 山东大学硕士学位论文 第五章图的m y c i e l s k i 图的均匀染色 给定图g = ( k 历) ，g 的m y c i e l s k i 图m ( g ) 被定义为一个新图：y ( m ( g ) ) = y u y u u ) ，其中v 7 = 曼，i v ) ；历( 彳( g ) ) = e u 【z 可7 i z 曰) u 【u 可i y ) ，称点y 7 为y 的复制点 图5 1 给出了忍的m y c i e l s k i 图 w 图5 1b 的1 1 4 y c i e l s k i 图 定理5 1 对 ，阶路r ( n 3 ) ，有x 。( m ( r ) ) = ( m ( r ) ) 证对路上的顶点从起点顺序为 t ，v 2 ，) ，为仇的复制点，u 为定 义中增加的点 对于 = 3 的时候，最大度为( 肘( 岛) ) = 4 ，给定一个染色妒，以下面的 规n - 妒似) = i 当i = 1 ：2 ，3 ； 妒( ) = i 当i = 1 ，2 ，3 ； 妒( “j ) = 4 ； 显然这个染色是正常，并且是均匀的 对于佗4 的时候，最大度为( ，( r ) ) = n ，给定一个染色妒以下面的 规则； p ( 钦) = i 当i = l ，2 ，弼 妒( u ：) = i 当t = 1 ，2 n ； 1 7 山东大学硕士学位论文 矽( u ) = 1 ； 这个染色不是正常的，顶点u 和顶点u 7 l 的染色相同因为顶点t ，1 仅和 顶点u 7 2 ，u 相邻，现在调整如下： 妒( u ；) = 3 至此，这个染色就是正常的了，并且是均匀的，除颜色3 外，每种颜色用 了2 次 故对1 7 , 阶路r ( 礼3 ) ，有x 。( m ( r ) ) = ( m ( r ) ) 口 定理5 2 对伽圈g 之3 ) ，有( m ( r ) ) = ( 肘( r ) ) 证对圈一卜的顶点顺序为 l j l ，忱，) ，t 为v i 的复制点，u 为定义中增 加的点 对于n = 3 的时候，最大度为a ( m ( c 3 ) ) = 4 ，给定一个染色妒以下面的 规则： ，v ( v i ) = i 当i = 1 2 ，3 ； 妒( u ：) = i 当i = l ，2 ，3 ； 妒( u ) = 4 ； 显然这个染色是正常，并且是均匀的 对于钆4 的时候，最大度为( 肘( g ) ) = n ，给定一个染色g o 以下面的 规n - 妒( 仇) = i 当i = 1 ：2 竹； 妒( ) = i 当i = 1 ，2 n ； 妒( u ) = 1 ； 这个染色不是正常的，顶点u 和顶点f 厂1 的染色相同因为顶点t ，l 的度 为3 ，仅和顶点v t 2 ，v t n 4 ) ，u 相邻，也就是说和染颜色3 的点不相邻，现 在调整如下： 妒( u i ) = 3 至此，这个染色就是正常的了，并且是均匀的，除颜色3 外，每种颜色用 了2 次 故对儿一圈“( ，。3 ) ，有x 。( m ( ( 名) ) = ( m ( c 名) ) 口 定义5 3g = ( k e ) 是一个简单图，i v i = n ，v ( v ) = v l ，坳， ， 如( g ) 称为图g 广义m y c i e l s k i 图，如果满足下面的条件： y ( ( g ) ) = 1 ，1 1 0 2 ，口l l t ，1 2 t ，1 。，咋l ，嘞，) ， 1 8 山东大学硕士学位论文 e ( m a c ) ) = ( u ( 件1 ) k l t 协咖七e ( g ) ，1 j ，k n ，i = 0 ：1 p 1 ) n ，p 2 ) 图5 2 给出了尸3 的广义m y c i e l s k i 图 图5 1 忍的广义m y c i e l s k i 图 定理5 4 对死阶路r 3 ) ，有( a 知( 只) ) = ( 知( r ) ) 证显然a ( m p ( p ) ) - - - 4 情况1p 是奇数时 子情况1 1i i 为偶数，定义如下染色法则p ： 妒( t 切) = 显然这是一个均匀 三0 ( r o o d2 ) 且j 三1 ( r o o d2 ) 三0 ( r o o d2 ) 且j 兰0 ( r o o d2 ) 兰1 ( m o d2 ) 且j 兰1 ( m o d2 ) 兰l ( r o o d2 ) 且j 兰0 ( r o o d2 ) 每种颜色用了n 0 + 1 ) 4 次 v p 3 子情况1 21 1 为奇数，对t 梳及其复制点重新染色，只需对上边的法则改 动如下： 显然是正常的，也是均匀 i 三0 ( m o d4 ) i 三1 ( r o o d4 ) i 三2 ( r o o d4 ) i 兰3 ( r o o d4 ) 1 9 嗽 坳 o o上