（计算机软件与理论专业论文）Cltmgt□Cltngt和Pltmgt□Cltngt的均匀全着色.pdf

大连理工大学硕十学位论文 摘要 图着色问题是图论的重要研究内容之一，也是一个n p 困难问题，并在组合优化等 方面有广泛的应用。经典的图着色问题只对顶点或边着色，随着在实际问题中的应用又 出现了新的着色问题，全着色就是其中之一。在这一研究领域，1 9 6 5 年b e h z a d 提出了 著名的全着色猜想( t c c ) ：对于简单图g ，其全着色数z 。( g ) 与最大度( g ) 之间的关 系为，z ( g ) a ( g ) + 2 。现已知对一些特殊的图类，如圈，完全图，完全二部图，外 平面图，最大度不为6 ，7 ，8 的平面图等猜想成立。 均匀全着色是全着色的一种特殊情况，在满足图g 可以k 全着色的基础上，还要 求每种不同颜色所染的顶点和边的个数相差不超过l 的最小整数k 称为g 的均匀全着色 数。1 9 9 4 年，h u n g 1 i nf u 最早给出了图的均匀全着色和均匀全色数的概念，他猜想任 意图g 当后m a x a 。( g ) ，( g ) + 2 时可以后等全着色，f u 自己证明了此猜想对树，完全 图，完全二部图等成立。w a n g 提出了关于均匀全着色的另一个猜想，对于图g ，有 z ( g ) ( g ) + 2 。并证明了最大度小于等于3 的多重图都可以5 等全着色。 c 卅口e 是两个长度分别为m 和r l 的圈的笛卡尔积图( 或称交图) ，对于这类图的全着 色前人已做过大量的研究。1 9 9 7 年，s e o u d 等人证明了当所3 ，y 为奇数或者3 的倍 数时z 。( 巳o c ) = a + i k e m n i t z 和m a r a n g i o 在2 0 0 3 年改进了这个结果，证明当m 3 ， 刀为5 的倍数时也满足z 。( c 卅o c ) = + l 。本文用计算机算法与数学分析相结合的方法 对图c 卅口e 的均匀着色进行了研究。通过不断改进搜索图巴口c 。的5 均匀全着方案的算 法的效率，尽可能多的计算出朋和刀足够大时结果，从中归纳出了一套对任意m 3 ， r 3 都成立着色方案。由此证明对任意整数m 3 ，r 3 图c 卅o c 的均匀全着色数为5 。 同时还对路径与圈的交图巴k i t n 的均匀全着色进行了研究，证明了当所3 ，r 3 时 只p c 的均匀全着色数也是5 。 关键词：笛卡尔积；全着色；均匀全着色 大连理工大学硕士学位论文 e q u i t a b l et o t a lc o l o r i n go fg 口g a n dp m d c n a b s t r a c t g r a p hc o l o r i n gp r o b l e mi sa m a i nr e s e a r c ha r e ao fg r a p ht h e o r y ，a n di sw i l d l ya p p l i e di n c o m b i n a t i o n a lo p t i m i z a t i o n i ti sp r o v e dt h a tg r a p hc o l o r i n gi sn p - e o m p l e t e t ot h ec l a s s i c a l g r a p hc o l o r i n g ，o n l yt h ev e r t e x e sa n de d g e sa r ec o n s i d e r e d w i t ht h ed e v e l o p m e n to f a p p l i c a t i o n ，n e wt y p e so fg r a p hc o l o r i n gp r o b l e ma r ep r o p o s e d t o t a lc o l o r i n gi sa ni m p o r t a n t o n eo ft h e m i n19 6 5 ，b e h z a ds h o w e dt h et o t a lc o l o r i n gc o n j e c t u r e ( t c c ) ：f o re v e r ys i m p l e g r a p hg ，z 。( g ) ( g ) + 2 w h e r e z 。( g ) i st h et o t a lc h r o m a t i cn u m b e ra n d ( g ) i st h e m a x i m u md e g r e eo fg c o n j e c t u r et c ci sp r o v e dt ob et r u eo n l yf o rs o m es p e c i a lc l a s s e so f g r a p h ，s u c ha sc i r c l e s ，c o m p l e t eg r a p h s ，t h ec o m p l e t eb i p a r t i t eg r a p h s ，o u t e r p l a n a rg r a p ha n d t h ep l a n a rg r a p h sw i t hm a x i m u md e g r e eu n e q u a lt o6 ，7 ，8 e q u i t a b l et o t a lc o l o r i n gi sas p e c i a lc a s eo f t o t a lc o l o r i n g t h ee q u i t a b l et o t a lc h r o m a t i c n u m b e ro fag r a p hgi st h es m a l l e s ti n t e g e rkf o rw h i c hgh a sak - t o t a lc o l o r i n gs u c ht h a tt h e n u m b e ro fv e r t i c e sa n de d g e sc o l o r e dw i t he a c hc o l o rd i f f e r sb ya tm o s to n e 19 9 4 ，h u n g - l i n f uf i r s ti n v e s t i g a t e dt h ee q u i t a b l et o t a lc o l o r i n ga n dc o n j e c t u r e dt h a tf o re v e r yg r a p hg ，gh a s a l le q u i t a b l et o t a lkc o l o r i n gf o re a c hk z ”( g ) ，( g ) + 2 h ep r o v e dt h ec o n j e c t u r eh o l d s f o raf e ws p e c i a lc a s e ss u c ha st r e e s , c o m p l e t eg r a p h sa n dt h ec o m p l e t eb i p a r t i t eg r a p h s w a n gp r o v e dt h a ti fg i sam u l t i g r a p hw i t hm a x i m u ma tm o s t3 ，t h e ngh a sa n5e q u i t a b l e t o t a lc o l o r i n g l e tg 口cb et h ec a r t e s i a np r o d u c to ft w oc y c l e sw i t hl e n g t hma n d 刀，al o to fw o r kh a s b e e nd o n eo nt h et o t a lc h r o m a t i cn u m b e ro ft h i sg r a p h s 19 9 7 s e o u de ta 1 p r o v e dt h a t z 。( c 卅口q ) 2 a + i f o rm 3a n d 疗b e i n ga n e v e nn u m b e r o r am u l t i p l eo f 3 2 0 0 3 ，k e m n i t z a n dm a r a n g i of u r t h e rp r o v e dt h a tz 。( g 口g ) = + lf o rm 3a n d 玎b e i n gam u l t i p l eo f5 t o o t h i sp a p e ru s e st h em e t h o di n t e g r a t i n gw i t hc o m p u t e ra n dm a t h e m a t i c a la n a l y s i st os t u d y e q u i t a b l et o t a lc o l o r i n go f 巳口q a na l g o r i t h mi sd e s i g n e db a s e do nt h ec o n d i t i o nt os e a r c h t h ec o l o r i n g w h e nma n d i sl a r g ee n o u g h b yi m p r o v et h ee f f i c i e n c yo ft h ea l g o r i t h mt o f i n da sm u c hc o l o r i n ga sp o s s i b l e i ti sp r o v e dt h a tt h ee q u i t a b l et o t a lc h r o m a t i cn u m b e ro f c 舸口q i s5f o ra l lm 3a n d ，3 t h ee q u i t a b l et o t a lc o l o r i n go fa n o t h e rc a r t e s i a n p r o d u c tg r a p h 己o c i ss t u d i e di nt h i sp a p e r , a n dp r o v e dt h a tt h ee q u i t a b l et o t a lc h r o m a t i c n u m b e r o f 乞口qi s5f o r a l lm 3a n dn 3 t o o k e yw o r d s ：c a r t e s i a np r o d u c tg r a p h ；t o t a lc o l o r i n g ；e q u i t a b l et o t a lc o l o r i n g i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：丝丝狸垫鱼盟塑鱼全羞鱼 作者签名：毖筮日期：迎盘年j 釜月2 生日 大连理工大学顾士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目：g 堡旦g 垒狸坐旦g 垒鲍塑鱼全羞鱼 作者签名：壅丝蕴 日期： 绝篁年l 月兰生日 导师签名：杰毒尘蓬支 大连理工大学硕十学位论文 引言 图论的产生和发展经历了二百多年的历史，是离散数学的骨干分支。以图论的第一 篇论文瑞士数学家欧拉的哥尼斯堡七桥问题( 1 7 3 6 ) 为代表，多数问题是围绕着游戏产生 的。图论所涉及的问题比较广泛，而解决问题的方法予变万化，非常灵活。现实世界中 的许多事物( 或对象) 能用图表示其拓扑结构，为分析处理多种问题提供一种较为理想的 数学模型。因此，图论在自然科学和社会科学的许多领域有着广泛的应用。特别是进入 2 0 世纪七十年代以后，计算机技术迅速发展。由于图论的算法易于借助计算机实现，二 者的结合使得图论的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、 控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面应用的研究都得 到“爆炸性发展”i l l 。 图的着色理论起源于1 8 5 2 年的“四色猜想” 2 1 ，即：在一个平面或球面上的任何地 图能够只用四种颜色来着色，使得没有两个相邻的国家着相同的颜色。后来，人们把国 家( 和外部区域) 都看成点，当两个国家相邻时，代表这两个国家的两个点之间就用一 条线来连接。这样，“四色猜想”就转化为图论中的着色问题，即每一个可平面图是4 - 可着色的。同时这也是图论着色问题中著名的“四色定理”。从此，图着色理论的研究 就一直在图理论中占有举足轻重的位置。 图的全着色是对图的顶点和边同时进行着色，使得相邻或相关联的元素得到不同的 颜色。是图的着色理论中的一个重要分支。1 9 7 3 年，m e y e r 提出了图的均匀点着色的概 念，从此揭开了图的均匀染色的序幕。所谓均匀着色，是在原着色条件的基础之上，还 要求每种颜色所染元素数相差不超过l ，其所用最少着色数称为均匀色数。1 9 9 4 年以来， 人们又先后提出了图的均匀边着色和图的均匀全着色的概念。 图的均匀全着色研究正在发展之中，目前所知重大结果并不多。本文在这些已有结 果的基础上研究了图q o c 和己q c 均匀全着色。给出了一套对于任意整数所3 ，3 都成立的着色方案并确定了这两类图的均匀着色数均为5 。 c m d c 和厶口g 的均匀全着色 1 基本概念和研究动态 1 1基本概念 1 1 1 图的基本概念 为了在本文的相关讨论中避免歧义，首先给出与本文研究内容相关的图论的一些基 本概念和定义。以下定义参考了文献【h 】。 一个图g 定义为一个二元组( 坎回，以g ) ) ，简记作g 毫( k d 。其中坎g ) 表示一个非空 的顶点集合；以回表示连接顶点的边集，其中每一条边与两个顶点相关联。若以g ) 中的 边与顶点的无序对( b ，v ，) 相关联，则称该边为无向边；著以回中的边与顶点的有序对 相关联，则称该边为有向边；每一条边都是无向边的图称为无向图；每一条边 都是有向边的图称为有向图；既有无向边，又有有向边的图称为混合图。 图g 中顶点的数目，称为图g 的阶；图g 中边的数目，称为图g 的大小。 图g 中的任意一条边( 甜，) 简记为“1 ，一般称”和 ，是相邻的顶点。称一条边的顶点 和这条边相关联。关联于同一个顶点的边称为自环，关联于同一对顶点的两条或两条以 上的边称为多重边。无自环，无多重边的图称为简单图。仅有一个顶点的简单图称为平 凡图。本文涉及到的图若无特别指出，均为无向简单图。 与顶点“v v ) 相关联的边数，称为该顶点的度，记作吠v ) ：其中顶点度中的最大 值称为图g 的最大度，记作( g ) ；顶点度中的最小值称为图g 的最小度，记作万( g ) 。 若吠吩= o ，称1 ，为孤立点。若政v ) = 1 ，称1 ，为悬挂点，与悬挂点关联的边叫悬挂边。若 v v 坎回，d ( v 净r ，则称图g 为r - 正则图。 图萨( 乃d 中萨邶l v i v k - l e k v k 表示顶点和边的一个交替排列，若l f k 时v i 1 ，聊为 与e ，邻接的顶点，则称w 为一条通路。若通路w 中的所有边都不同，则称w 为一条迹。若 迹w 中的所有顶点也均互不相同，则称w 为一条路径，含刀个顶点的路径记作一。 又若迹w 的起点和终点相同( 岵均，其他顶点都互不相同且k 3 ，则称它为一个圈( 或 回路) 。一个圈中边的个数称为这个圈的长度，长度为刀的圈记作g 。图g 的围长是指在 图g 中最短的圈( 假如g 中有圈) 的长度。 若一个图的每一对顶点都有一条路径连接，这个图称为是连通的。g 的一个极大连 通子图称为g 的一个连通分量。一个连通图只有一个连通分量，那就是它自身。 一个图的一个割点是这样一个顶点：移去它后使剩下的图的连通分量的数目比原来 的图有所增加。一条割边也是具有类似性质的一条边。无割点的连通图称为( 点) - - 连通 大连理工大学硕士学位论文 图。g 的极大二连通子图称为g 的二连通分量。连通的、非平凡的而且没有割点的图称 为不可分图。图g 的一个极大的不可分子图称为图g 的一个块。 下面介绍几类常见的图：一个连通的且无回路的图称为树。每对不同顶点均有一 条边相连的简单图叫做完全图，含刀个顶点的完全图记作k 。一个图的顶点集v 若能 分成两个非空子集x 和l 使x u 净儿x n 弘，且g 的每条边的两个端点分别在x 和】，中，则称此图为二部图，记为。其中特殊的墨。称为星图。 对图g 和凰如果坎肋坎g ) ，e ( h ) c e ( g ) ，则称日为g 的子图，记为埏g ；如 果坎奶坎g ) 或e ( h 净e ( o d ，称h 为g 的真子图，记为h c g 。如果坎奶= 坎g ) ，e ( h ) c e ( o d ， 则称日为g 的生成子图；如果v ( 1 - 1 ) c 坎回，当且仅当群 ，戤回且u , v e 坎1 4 ) 时，材y 以伪 则称日为g 的导出子图。 定义i i 交图和联图 两个图g i 和g 2 的笛卡尔积得到的图称为两个图的交图，记为g l n g ( 在某些文献 中，也用“”表示图的笛卡尔积) 。交图g _ g l 口g 是满足以下条件所构成的图类： ( 1 ) g 的顶点集坎g ) = ( 甜，功i 对于任意g g l ，v g 2 ) ； ( 2 ) 对于任意萨( “。，“：) v ( g ) ，一h ，屹) g ( g ) ，当= 且吃和在g 2 中相邻或 u z = v 2 d u i 和q 在g l 中相邻时，2 ，和y 在g i o g , 中相邻。 联图岱g i + g 2 是满足以下条件所构成的图类： ( 1 ) g 的顶点集坎g ) = y ( g 1 ) uy ( g 2 ) ； ( 2 ) g 的边集顾铲e ( g i ) ue ( g 2 ) o u p i 材e ( g 1 ) ，v e ( g 2 ) ) 1 1 2 图着色的基本概念 定义1 2 点着色 给定图叫k d 中，称映射万：矿_ o , z 一3 ，k ) 为g 的一个k 点着色，简称着色。称 l ，2 ，3 ，k 为色集，用v f 表示着颜色i 的顶点的集合。若对任意相邻顶点甜，均满足， 万 ) 万( 1 ，) ，则称该着色是正常的，图g 的正常楮色的最小难称为g 的色数记为z ( g ) ， 简记为z 定义1 3 边着色 给定图g = ( 旧中，称映射石：昱一0 , 2 3 ，k 为g 的一个七边着色，简称边着色。称 l ，2 ，3 ，k 为色集，用局表示着颜色i 的边的集合。若7 c 为g 的边着色且对任意e 。，e ，e g a g 和厶3 g 的均匀全着色 当e 。与p ：相邻时，万( q ) 万( p ：) ，则称该着色是正常的，图g 的正常触着色的最小艟称 为g 的边色数记为z ( g ) ，简记为z 定义1 4 全着色 给定图g = ( k d 中，称映射7 r ：矿u e 一0 , 2 3 ，七) 为g 的一个k 全着色。如果还满足 下列条件： ( 1 ) v u v e ，有顽材) 反，) ( u - - l - v ) ，n ( u o n f v ) ，积甜彬砜甜) ； ( 2 ) v u v 7 ，u v 。e ，有万( 删) 万( w ”) ( u v z n ，。) 则称着色7 r 是正常的。图g 的正常k 全着色的最小七值称为g 的全色数，记为( g ) 定义i 5 均匀着色( 又称为等着色) 给定图g = ( v ，e ) ，对它的一个正常措色万：v - - - ) 0 , 2 3 ，k ) ，v i 表示着颜色i 的顶点 的集合，即杉= v l ，y ( g ) ，万( ，) = 磅。如果满足对任意f ， l ，2 ，3 ，k ) 都有 0ki - l 匕i i l ，则称7 r 是图g 的一个k 均匀着色。图g 的七均匀着色的最小碹称为g 的均匀 色数，记为九( g ) 定义1 6 均匀边着色 给定图g = ( v ，e ) ，对它的一个正常勉着色藏：y _ 0 , 2 3 ，k ) ，e j 表示着颜色i 的顶 点的集合，即互= 删iu v e ( g ) ，万( 甜1 ，) = f 。如果满足对任意， l ，2 ，3 ，k ) 都有 0 互| _ ie ，i i 1 ，则称棍图g 的一个k 均匀着色。图g 的胸匀着色的最小植称为g 的均匀 色数，记为z ( g ) 定义1 7 均匀全着色 给定图g _ ( 儿d 对它的一个映射石：矿u e 专0 , 2 3 ，砖，若满足下列条件： ( 1 ) v 价，e ，有y ( u ) - - - ( o ( ；荆，( u v ) - - ：o ，灭豁d 预力； ( 2 ) v u v ，z n ，。e ，有( 枷) f ( u v ”) ( u v z n ，。) ； ( 3 ) v i ， l ，2 ，3 ，k ，有0zl - i 乃i l 1 ，其中霉= ku 蜀，形= ，l ，y ( g ) ，万( 1 ，) = 磅， 互= u v i l f l ，e ( g ) ，万( 1 ，) = 磅 则称万是图g 的一个k 均匀全着色。图g 的k 均匀全着色的最小k 值称为g 的均匀全 着色数，记为彤( g ) 大连理工大学硕士学位论文 1 2 图的着色问题 图的着色起始于“四色猜想”，从提出至今很多人都试图证明此猜想的正确性，但只 得到了一些部分的结果。1 9 7 6 年，在无数尝试和部分结果的基础上，美国伊利诺大学的 a p p e l ，h a k a n 和k o c h 等人终于借助电子计算机花费了大量时间证明了这一猜想的成立 1 4 1 。1 9 9 7 年，r o b e r t s o n ，s a n d e r s 和t h o m a s 又给出了此猜想的一个简化的计算机证明l 引。 但人们仍然没有放弃对严格数学证明的探索，迄今“四色问题”也仍未划上句号。由此 也可以看出，使用计算机辅助是解决图的着色问题的一个十分有效手段，图论中的很多 算法都可以用计算机来实现。并且有着广阔的发展前景。 近几十年来，关于图着色问题的研究得到了许多有趣而实用的结果，以由最初的点 着色和边着色拓展出若干新的着色分支。将过去未解决的问题转化为一个个新的着色问 题。如全着色，无圈着色、可区别边着色、列表着色、对策着色、邻强边着色、均匀着 色和均匀全着色等。 1 9 6 5 年b e h z a d 7 l 和v i z i n g 【8 1 分别独立提出了著名的全着色猜想( t c c ) ：对于简单 图g ，不等式z 。( g ) ( g ) + 2 成立，即图的g 全着色数，不大于它的最大度加2 。围绕 这个猜想，人们开展了对图的全着色问题的研究，得出了许多有用的结果。一方面证明 全着色猜想对某些特殊图类是成立的，如树、圈、星、完全图、完全二部图、完全k 部 图、一些图的合成图( 如，刀条路径的合成图和刀个圈的合成图) 和联图( 如，两个圈的 联图) 等网。 另一方面证明了对一般图类在一定限制下全着色猜想是成立的。例如对最大度作一 定的限制，现主要分为高度和低度两个方向。1 9 7 1 年r o s e n f e l d 和v i j a y d i t y a 研究了低度 图的全着色，他们分别独立地得到对简单图当( g ) 3 时，全着色猜想成立的证明；1 9 7 7 年时，k o s t o c h k a 把这个结论向前推进一步，证明了对于多重图，当( g ) 4 时全着色猜 想成立；到1 9 9 6 年k o s t o e h k a 又把结果推进到，对( g ) 5 的多重图全着色猜想都成立。 简单图可以看做重数为l 的图，是一种特殊的重图，因此这就证明了当最大度小于等于 5 时，全着色猜想对于低度简单图是成立的。相对于低度图来说，高度图的结论就更丰 富些。主要成果有【协1 a ( g ) 眇( g ) l _ 5 、a ( g ) 3 i v ( g ) i 4 时图的全着色猜想成立； ( g ) 9 和( g ) = 7 时对于平面图全着色猜想成立。但是完全证实全着色猜想，实在是 非常困难的，这是一个远未解决的问题。 图的均匀着色是图的着色理论的一种特殊情况。所谓均匀着色，是在原染色条件的 基础之上，还要求每种颜色所染元素个数相差不超过l ，其所用最少颜色数称为均匀色 数。 g 口g 和厶口g 的均匀全着色 在1 9 6 4 年，e r d 6 s 猜测：对于一个图g 和整数k ，当k ( g ) + l 时，图g 可以用斛1 种颜色均匀着色，任意图均匀着色数苁( g ) s ( g ) + l 。这一猜想于1 9 7 0 年被h a j n a i 和 s z e m e r 6 d i 所证吲引。最近，k i e r s t a b l e 和k o s t o c h k a 对这个定理给出了一个较短的证明并 且得到了一个更强的结果【1 4 】： 如果图g 中所有的边u v e 以回都满足吠甜) 坝v ) 2 什1 ，则图g 的均匀色数 厄( 6 3 a ( 6 3 + 1 在此基础上1 9 7 3 年，m e y e r 提出了图的均匀点着色的如下猜想f l5 1 ，如果一个图g 既 不是奇圈c ：川也不是完全图k 。，那么它的均匀色数厄( g ) a ( g ) 。对于这一猜想现已 证明：它对一部分特殊的图类，包括树5 1 ，二部图【1 6 】，完全后部图5 1 ，外平面刚17 1 ，a ( g ) 1 3 的平面图，a ( g ) 3 的图和( g ) i v ( g ) 2 的图【5 】等是成立的。 1 9 9 4 年，有人又提出来另一个猜想( a e c c ) ：如果一个图既不是奇圈c m ，也不是完 全图k 。和二部图k 2 州加+ 。，则图g 的均匀色数石( g ) a ( g ) 。这个猜想也同样是只有部分 情况得到证日月【1 5 】。 y a p f 6 q y i o s l 证明了a e c c 猜想对外平面图成立，同时他们还迸一步猜测：对于外平 面图g ，如果( g ) 3 且七i + a ( g ) 2 ，则图g 是胸匀可着色的。这个猜想的正确性随 后得到了证明。 而对于平面图，y a p 和y i t l s 】也给出了一个非常漂亮的结果：给定平面图g ，如果 ( g ) 1 3 ，则图g 是( g ) 均匀可着色的。 关于均匀着色还有一些关于合成图的结论f 4 ，如路径和偶圈的合成图可以砌匀着色 ( 勉) ，路径和奇圈的合成图可以砌匀着色( 硷3 ) ，圈和圈的合成图可以瑚匀着色( 砭3 ) 等。 1 9 9 4 年以来，人们又先后提出了图的均匀边染色和图的均匀全着色的概念。目前已 证明，图的均匀边色数等于它的正常边色数( 即苁( g ) = z ( g ) ) 。而经过多年的研究，图 的正常边染色理论研究已趋于成熟和完善，有著名的v i z i n g 定理：若g 是简单图，则 一定有z ( 6 3 = a ( 6 3 或z ( g ) = ( 回+ 1 。从而对于图的均匀边染色研究等同于图的正常 边染色研究，只要考虑什么图属于第一类，什么图属于第二类就可以了。 1 3 图的均匀全着色的研究动态 1 9 9 4 年，h u n g l i n t l 9 】最早给出了图的均匀全着色和均匀全色数的概念。1 9 9 6 年，张 忠辅在天津南开大学数学研究所“组合数学与图轮”学术会议上作学术报告时也独立地 大连理丁大学硕士学位论文 提出了这些概念。他们在研究了一些简单图的均匀全色数后提出了均匀全着色猜想：任 意简单图的均匀全色数至多为a ( g ) + 2 ，且以。( g ) = z 。( g ) 。自此揭开了图的均匀全着色 研究的序幕。 h u n g l i n t l 9 1 首先研究了图的均匀全着色，并提出了下面的猜想：给定图g ，若 七 ( g ) ，a ( g ) + 2 ，则图g 有一个瑚匀全着色。并证明了这个猜想对一些特殊图类是 成立的，例如树，完全图，完全二部图，a ( g ) l y ( g ) | - 2 的图等。同时，他注意到存在 许多满足全着色数z 。( g ) = ( g ) + l 却不能( g ) + l 均匀全染的图g 在此基础上，王维凡提出了如下猜想：对于图g ，有彤( g ) ( g ) + 2 。此猜想与著 名的提出的著名的全着色猜想统一了起来。他还研究了树、完全二部图、完全多部图以 及( g ) 3 的无环多重图的均匀全着色，证实了在这些情况下上面的均匀全着色猜想成 立。 图的均匀着色应该算是一个比较新的概念，从提出至今也不过发展了1 0 几年，才 刚刚起步，因此重大成果并不是太多。目前已知的结论如下 2 0 - 2 6 】： 对于图g 的口- 图的均匀全着色猜想成立，即：对0 - 图g 有z ( g ) = z 。( g ) = 4 ：“ 对完全二部图如有z ( g ) = m a x m ，栉) + 1 + 万( 聊，功，其中万( 聊，刀) ( m ，n ) 是图的 k r o n e c k e r 函数。 广义等星图g ，z ( g ) = n + 1 轮图的均匀全色数： 彤( 形) = 刀= ( ) + 1 扇图的均匀全色数： z ( e ) = n - - - - ( e ) + 1 完全图的均匀全色数： 抛，= 会：臻 星图的均匀全色数： 以c 白，开，= 会：三：， 对于图的m y c i e l s k i 图的均匀全着色问题，已研究了路、星、轮扇等图的m y c i e l s k i 图的均匀全色数，主要结果有：z ( m ( 只) ) = ( m ( 只) ) + l ；彤( m ( 鼠) ) = ( m ( 瓯) ) + l ( 刀2 ) ；z ( m ( 形) ) = 袱m ( c ) ) = 2 n + l ( 刀3 ) c 二3 g 和j p o o g 的均匀全着色 对于简单图g ，若( g ) ：爿y ( g ) l _ l ，且g 仅有一个最大度点，则( g ) = ( g ) + l 。 这是z ( g ) = ( g ) + l 的一个充分条件。由此条件可得到了一些一阶简单图的联图的均匀 全色数。 两条路径的联图： f 3 ， 胪l ， z ( 仇v p 。) = 5 ， 刀= 2 ， b + 3 ，n 3 路径与圈的联图：z ( v e ) = 刀+ 4 ， 眨3 两个圈的联图：( qv c n ) = 刀+ 4 ， n 3 路径与星图的联图：彤( 只vk 。) = 2 n + l ， 蹦 路径与扇图的联图：z ( v c ) = 2 n + l ， 眨3 圈与扇图的联图：( eve ) = 2 n + l ，幽 路径与轮图的联图：z ( 只v 既) = 2 n + l ，西 圈与轮图的联图：z ( ev 形) = 2 n4 - l ，西 简单图g 和日中，若a ( g ) 爿v ( g ) i _ l ( 或a ( h ) = v ( h ) i - i ) ，i q ( i v ( g ) i + i 坎豳) ) = l ( m o d2 ) ，则z ( g v h ) = i 坎回i4 - iv ( h ) i 。此结论可以推广到多个图的联图，即对于简 单图g l ，g 2 ，g ，存在九 l ，2 ， 使得( q ) = 爿y ( g ) l + l 且 l y ( v ：。q ) l - 2 。i y ( g j ) 1 1 ( m o d 2 ) ，则z ( v ：。g ) = r = 。1 y ( g ) i 。 简单图g 和日中，若a ( g ) 爿v ( g ) i - 1 ，a ( h ) qy ( 日) f - 2 ，且g 只有一个最大度点，则 z ( g v 均= i 坎回i4 - i v ( h ) i 。 对于简单图g ，若( g ) 爿矿( g ) i - l ，且i 坎回i = 1 ( m o d 2 ) ，则z ( g ) = ( g ) + l 。 对于简单图g ，若( g ) 爿y ( g ) i - 2 ，则z ( g ) l v ( g ) l 。 设是刀阶路径，k 是自然数，当且仅当两顶点距离为吠v ，) = 七时添加边u ，所得 到的图称为露。当以2 k + l ，i t 5 时z ( 露) = 5 = + 2 。 路与完全二部图的联图的均匀全色数： 彤c 己v 毛，。，= 龛 乏：乏二；：三，：三：二主： 轮图与路径的联图的均匀全色数： 大连理t 大学硕十学位论文 z c 呒v ，= 二i 竺：亍二+ 。， 星图与轮图的联图的均匀全色数： z ( 既v 瓯) = f 聊7 = + a m + 2 , ：川， 星图与路径的联图的均匀全色数： z ( 己v 鼠) = r l = 2 ，m = 3 ， 其余 刀= l ，m = 3 ， 其余 m + 2 ，m = l ， 5 ， m = 2 ，”= 1 ， m + 3 ， m = 2 ，刀之2 ， m + ”+ l ，m 3 星图与圈的联图的均匀全色数：， 抛v 驴 ：黧州，玎嚣3 星图与完全二部图的联图的均匀全色数： 胛 ，_ 麓三一。，刀嚣1 路径与扇图的联图的均匀全色数： f 5 = a + 2 ， 刀= 2 ，m = l ， 彤( 名v c ) = 7 = a + 2 ， 刀= 2 ，m = 3 或m = 2 ，= 3 ， i m + 刀+ 1 = a + i ，其余 圈与扇图的联图的均匀全色数： 肥v 耻腮：k 。，肛蓉3 ， 圈与轮图的联图的均匀全色数： 当m 3 ，刀3 时，z ；c c v 形) = m + n + l = a + i 圈与轮图的联图的均匀全色数，z ( q v 形) = 历+ 刀+ l - + 1 以上研究都证实了对一些特殊图类均匀全着色的猜想z ( g ) ( g ) + 2 成立，但要证 明此猜想对一般图都成立同样是一个十分困难的问题。 g 口g 和厶a g 的均匀全着色 1 4 本文工作 对一般图均匀全着色的研究是很困难的，已有的成果主要是对特殊图类给出具体的 均匀全着色映射方案来，再对其进行证明。本文对两类图的交图的均匀全着色问题进行 了研究。 本文采用计算机辅助计算来得到均匀全着色映射方案。图着色的计算是个n p 问题， 当m 和刀比较大时计算出结果就需要很长时间。本文采用分支限界策略来加快计算速度， 并对m 和捍较小时的结果进行归纳，分析，找出其中可能的规律，再用这些规律修改限 界条件。通过这样反复的计算和修改，最后得到所求的图的一个均匀全着色的映射方案。 并证明了对于任意整数m 3 ，1 1 3 ，图巳口q 和巴o c 的均匀着色数均为5 。 大连理工大学硕士学位论文 2 细c o 的均匀全着色 c 卅和g 分别表示长度为聊和甩的两个圈，它们的笛卡尔积g o c 是一个有m 个顶点 的4 - i e 贝j 。它的顶点用k ，来表示，其中0 f 刀一l ，0 坍一l 并且，分别对门和 m 取模。 c 5 d e , 如图2 1 所示。 图2 1 f i g 2 1 go c , go c , 对于这类交图的着色问题，前人已经做了很多的研究f 2 7 2 钔。其中1 9 9 7 年，s e o u d i 正 明了对于图c 卅o c ，当i t 3 ，l 为奇数或者3 的倍数时( c 卅o c ) = a + i 。2 0 0 3 年， k e m n i t z 和m a r a n g i o y , i 正明了对于图q p c ，当m 3 ，刀为5 或者5 的倍数时 z 。( q 口g ) = a + i 。b a r i l 等人给出了对于任意圈的笛卡尔乘积图，它的邻点可区别着色 数为+ 1 下面我们考虑图q 口g 的均与全着色，首先把m 和刀分别对5 取模，分成mm o d5 = 0 、 m o d5 = 0 ，mm o d5 = 0 、拧m o d5 = 1 ，mm o d5 = 4 、1 m o d5 = 4 ，2 5 种情况来讨论问 题。由于q 口c 有着很好的对称性，这给我们解决问题带来了很大的方便，可以大大减 少需要讨论的情况，只要考虑mm o d5sr m o d5 的情况即可。 为阐述方便，先说明一下本文中需要用到的各种符号表示： c 坍口g 和厶a g 的均匀全着色 对于图巳口e ，令v = v ，l0 jsn - 1 ，0 ，m - 1 ) 表示图中的顶点集合，v ，表示 其中的任意一个顶点。 我们把c 埘口e 的边集分为两组： e - = m ，j e 。p l1 0 i 刀一l ，0 j ，”一1 ) ； e = h q + l ，j1 0 i b - i ，0 j m i ； 其中厶，分别对n 和m 取模。 届，屈，屈，厦，层表示5 个整数序列： 层= 1 2 3 4 5 ，履= 2 3 4 5 1 ，屈2 3 4 5 1 2 ，屈= 4 5 1 2 3 ，屈= 5 1 2 3 4 石：为一个映射，表示图巳口g 的一个着色。 2 1历对5 取模得0 引理2 1 对任意m 3 ，疗3nmm o d5 = 0 ，图q 口e 可以5 均匀全着色。 证明：当mm o d5 = 0 时在按照玎对5 取模的结果分情况讨论，考虑到mm o d5 力 m o d5 ，在这里我们有5 种情况需要考虑。 为表述方便，我们先定义在结果中多次循环出现的整数序列： 里竺里竺竺 如= 届5 屈5 屈5 屈5 屈， 竺竺竺苎 竺 s e = 屈5 届5 屈5 层5 届5 苎苎苎竺竺 瓯。= 屈5 属5 届5 孱5 屈5 情况1 疗m o d 5 = 0 此时，定义映射石如下： ! 万( y ) = ( 砜) 5 ， 竺 万( 疋) = ( 瓯。) 5 ， 苎 万( e ) = ( 阮。) 5 图2 2 显示了7 c ( c 5 口c 5 ) 的着色情况。 首先我们要证明7 c 是一个正常的全着色。 对露的任意一条边匕。，万( k ) 和刀( k ) 分别表示与万( ) 中边哆， + 。的着色对 应的顶点一，和e + l 的着色。其中o i n 一1 ，0 j m - i 并且，j 分别对n 和聊取模。 大连理工大学硕十学位论文 图2 2 顽go g ) f i g 2 2 顽c 5 0 c , ) 万( e ) = “3 4 5 1 2 ) 5 ( 1 2 3 4 5 ) 5 ( 4 5 1 2 3 ) 5 ( 5 1 2 3 4 ) 5 ( 2 3 4 5 1 ) 5 ) 5 ， 苎翌竺苎竺旦 刀( k ) = ( ( 1 2 3 4 5 ) 5 ( 3 4 5 1 2 ) 5 ( 5 1 2 3 4 ) 5 ( 2 3 4 5 1 ) 5 ( 4 5 1 2 3 ) 5 ) 5 ， 苎 竺 苎竺苎三 万( 砭) = ( ( 4 5 1 2 3 ) 5 ( 2 3 4 5 1 ) 5 ( 5 1 2 3 4 ) 5 ( 1 2 3 4 5 ) 5 ( 3 4 5 1 2 ) 5 ) 5 显然v m ，v 1 j + l ，瓦，有万( v ，j ) 万( 哆“) ，万( b ，j ) 万( m ，j v l j + 1 ) ，万( 峙，哆。，+ i ) 万( m ，p 1 ) 对e 的任意一条边畴。j e + l j ，万( 巧) 和万( k ) 分别表示与万( e ) 中边匕，h 小的着色对应 的顶点k ，和v ，+ l ，的着色。其中0 i n - i ，0 m - 1 并且i ，j 分别对力和m 取模。 里苎里!苎翌 万( e ) = ( ( 4 5 1 2 3 ) 5 ( 2 3 4 5 1 ) 5 ( 1 2 3 4 5 ) 5 ( 3 4 5 1 2 ) 5 ( 5 1 2 3 4 ) 5 ) 5 ， 竺 竺 苎!竺苎 万( k ) = ( ( 1 2 3 4 5 ) 5 ( 3 4 5 1 2 ) 5 ( 5 1 2 3 4 ) 5 ( 2 3 4 5 1 ) 5 ( 4 5 1 2 3 ) 5 ) 5 ， 里竺竺竺竺! 刀( 圪)