（运筹学与控制论专业论文）关于图的邻点可区别全染色问题的研究.pdf

摘要 关于图的邻点可区别全染色问题的研究 摘要 图的染色问题是图论的主要研究内容之一，在地图染色、交通 定向和计算机网络等领域有广泛的应用图的染色的基本问题就是确 定其各种染色法的色数图的邻点可区别全染色就是要求相邻顶点具 有不同颜色集合的正常全染色张忠辅教授等最先提出图的邻点可区 别全染色这个概念，并猜想x 。t ( g ) x ( c ) + 3 本学位论文首先主要针对几个特殊图类讨论其邻点可区别全色 数，验证了其满足图的邻点可区别全色数的猜想；再证明了非轮的 h a l i n 图的邻点可区别全色数：接着研究的是广义p e t e r s e n 图，讨论了 不能构成广义p e t e r s e n 图的几类正整数( n ，纠，并证明了该图的邻点 可区别全色数等于5 ；最后，根据图所含圈的个数及其奇偶性得到了 两类图的邻点可区别全色数 关键词：点染色，边染色，全染色，邻点可区别全染色，邻点可区别全 色数 a b s t r a c t s t u d yo nt h ep r o b l e mo fa d j a c e n t v e r t e x - d i s t l n g u i s h i n gt o t a lc o l o r i n go f g r a p h s a b s t r a c t t h ec o l o r i n gp r o b l e mo f g r a p h si si n d u c e db yc o m p u t e rs c i e n c e ，w h i c h h a sw i d e l ya p p l i c a t i o ni nn e t w o r k s t h ea d j a c e n tv e r t e x - d i s t i n g u i s h i n g t o t a lc o l o r i n gi st h ep r o p e rt o t a lc o l o r i n gw h i c hd e m a n d st h ea d j a c e n tv e t - t i c e sw i t hd i f f e r e n tc o l o rs e t s t h en o t i o no fa d j a c e n tv e r t e x - d i s t i n g u i s h i n g t o t a lc o l o r i n gw a si n t r o d u c e df i r s t l yb yp r o f e s s o rz h a n gz h o n g f ue ta li n 2 0 0 4 ，a n dt h ea u t h o r sc o n j + e c t u r e dt h a tx d t ( g ) z x ( a ) + 3 i nt h i sm a s t e rt h e s i s ，w em a i n l yd i s c u s st h ea d j a c e n tv e r t e x - d i s t i n - g u i s h i n gt o t a lc h r o m a t i cn u m b e r so fs o m es p e c i a lg r a p h sa n dp r o v et h a t z h a n g sc o n j e c t u r eh o l d s f o rt h e s eg r a p h s t h e nw e g e tt h ea d j a c e n t v e r t e x - d i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e r so f t h eh a l i ng r a p h s m o r e o v e r , w e i n v e s t i g a t et h eg e n e r a l i z e dp e t e r s e ng r a p h s ，p r o v et h a ts o m ec l a s s e so f p o s i t i v ei n t e g e r sc a n ts t r u c t u r et h eg e n e r a l i z e dp e t e r s e ng r a p h sa n dg e t t h er e s u l tt h a tt h ea d j a c e n tv e r t e x d i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e ri s 5 f i n a l l y , b a s e do nt h en u m b e ra n dt h ep a r i t yo fc i r c l e sc o n t a i n e db yt h e g r a p h ，w eg e tt h ea a j a c e n tv e r t e x - d i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e ro f t w oc l a s s e so fg r a p h s k e yw o r d s ： v e r t e xc o l o r i n g ，e d g ec o l o r i n g ，t o t a lc o l o r i n g ，a d j a c e n t v e r t e x d i s t i n g u i s h i n gt o t a lc o l o r i n g ，a d j a c e n tv e r t e x - d i s t i n g u i s h i n gt o t a l c h r o m a t i cn u m b e r i i 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。 研究生签名：王名舀番 日期：fd 分 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影印、缩 印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方式在不同 媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后遵守此协议。 研究生签名：王名艮壶 翩躲未i 逮渗期：7 2 、男 、绪论 一、绪论 图论是组合数学的一个分支。在现实世界中有着十分广泛的应用图论的诞 生即由瑞士数学家欧拉解决哥尼斯堡七桥问题而引发 由于图论特殊的起源，早期图论与“数学游戏”密切联系直至1 8 4 7 年， k i r c h h o f f 运片j 于t 程技术领域1 8 5 7 年，c a y l e y 在有机化学领域计算饱和氧化物 g 凰。+ 2 的同分异构体数目时，发现了后来被称之为“树”的一族苇耍的圈从 此，图论脱离了只解决“数学游戏”的阶段，开始麻用于解决各种实际问题，并向 诸多科学领域渗透，如物理学、化学、信息学、运筹学、博弈论、计算机网络、 社会学、语言学等2 0 世纪5 0 年代，计算机的飞速发展，促进了组合学最优化算 法研究，强力推动了图论的发展，从而使图论成为数学领域中发展最快的分支之 图的染色是图论的主要研究内容之一，在无线电通讯频道分配、舰队维护、 任务分派、交通定向等诸多领域有着广泛的应用图的点可区别染色问题是图的 众多染色问题中的一个特殊问题，最初由计算机科学等引出，是一个十分困难的 问题。在刊物上发表的文献一直较少在减弱了点可区别染色问题的条件后，得到 图的邻点町区别全染色的概念 ( 一) 、邻点可区别全染色问题的研究概况 简单幽g 的一个正常七一染色是指一个映射，：v ( c ) 一 l ，2 ，南 ，使得 对图g 中任意两个相邻的顶点们e ( g ) ，有i ( u ) ，( ) 称x ( g ) = m i n k i 图 g 有一个正常k 一染色为图g 的点色数 关于图g 的点色数有一个非常著名的b r o o k s 定理： 定理1 1 【j 对任意的图g ，有x ( c ) z x ( g ) + 1 ，等式成立当且仅当图g 为奇圈 或完全图 简单图g 的一个正常七一边染色是指一个映射，：e ( g ) 一 l ，2 ，七 ，使 得刘图g 中任意两条相邻的边e 1 ，e 2 ，有f ( e 1 ) ，( e 2 ) 称灭7 ( g ) = m i n k l 图g 有一个正常七一边染色，为图g 的边色数 关于图g 的边色数有一个非常著名的v i z i n g 定理： 、绍论 定理1 2 怯3 】对任意的简单图g ，有a ( g ) x 7 ( g ) ( g ) + 1 若x 7 ( g ) = ( g ) ，则称图g 是第一类的；若) ( ( g ) = a ( g ) + 1 ，则称图g 是 第二类的 定义1 1 设g 足阶至少为2 的连通图，k 是正整数，是v ( g ) ue ( g ) 到 l ，2 ，七) 的映射，对任意u y ( g ) ，记c ( u ) = ，( u ) ，u ，( u ) f “t ，e ( g ) ， y ( g ) ) ，叫做点“的颜色集合；- c ( t ) 表示点乱在全体颜色集合e 中的补集如果 ( z ) 对任意的w ，v w e ( g ) ，u w ，有，( ) ，( ) ； ( i i ) 对任意的u 口e ( g ) ，有，( “) ，( u ) ，( “) y ( u v ) ，( ) f ( u v ) ，则 ，称为g 的正常七一全染色，称x t ( g ) = m i n k f 图g 有一个正常七一全染色) 为 图g 的全色数进一步，如果，还满足 ( 俐) 对任意的t ，u y ( g ) ，“t ，有c ( u ) g ( 口) ，则称，为g 的七一点可 区别全染色( 简记为k - - v d t c ) 称m i n k l g 有七一点可区别全染色为g 的点可 区别全色数，记作x 。( g ) 定义1 2 4 1 如果把上面定义中的( 讹) 改为( i i i ) 7 ：对任意的w e ( g ) ，有 g ( u ) g ( 口) ，则称，为g 的七一邻点可区别全染色( 简记为七一a v d t c ) 称 m i n k l g 有七一邻点- 口r 区别全染色) 为g 的邻点可区别全色数，记作x 。t ( g ) 根据图的邻点可区别全染色的定义，有下面几个定理成立 定理1 3 4 】对任意的简单图g ，有x 。t ( g ) ( g ) + 1 定理1 4 州若图g 有两个相邻的最大度顶点，则地t ( g ) a ( c ) + 2 定理1 5 哪若图g 有七个连通分支g 1 ，g 2 ，一，g ，且i v ( g ) l 2 ( i = 1 ，2 ，一，七) ，则x 。t ( g ) 一m a x x 。t ( g 1 ) ，x 毗( g 2 ) ，x 。t ( g 詹) ) 基于定理1 5 ，接下来只需要讨论阶不小于2 的简单连通图的邻点可区别全 色数定理1 3 和定理1 4 给出了连通图g 的邻点可区别全色数的下界张忠辅 教授等【4 】证明了圈、完全图、完全二部图、扇、轮、树的邻点可区别全色数 下面足完全图的邻点u 区别全色数定理 定理1 6 【4 】设表示n 阶完伞图，n t , 一0 ( m o d 2 ) ； n l ( m o d 2 ) 1 2 + + n n ，fl、 i | 耐 x u贝 _ 文 2 一 绪论 由于已经证明的图的邻点町区别仝色数都小于或等于a ( a ) + 3 ，冈此张忠 辅教授等提出下面猜想： 猜想【4 】对于阶不小于2 的简单连通图g ，有x 。t ( g ) a ( g ) + 3 因为奇数阶完全图的邻点可区别全色数等于( g ) + 3 ，所以如果猜想成立， 这个上界就是紧的不过这仍然是一个困难的问题，目前所得到的结论也大都是 关于特殊图类的见义献 5 - - 1 1 】对于一般图，还没有一种有效的方法能刻画出其 邻点可区别全色数张少君等 1 2 给出了a ( g ) = 5 的2 一连通外平面图的邻点 可区别全色数安明强【1 3 】得到了z x ( a ) 一6 的2 一连通外平面图的邻点町区别 全色数 定理1 7 【”】设g 是( g ) 一5 的2 一连通外平面图，则 f 6 ， x m ( g ) = 【7 ， e ( g 【l ，】) = 0 ； e ( g 1 ，】) 0 定理1 8 1 3 1 设g 是a ( g ) = 6 的2 一连通外平面图，则 ( 二) 、基本概念 以g ) ： ，7 ， 【8 ， e ( g 【l ，】) = 班 e ( g v a 】) 毋 本节将定义一些奉学6 y _ 论文要用到的图论的基本术语和符号 本学位论文讨论的图均是无向有限简单图无向图是一个有序对g = ( v e ) ，其中y 是一个有限集合，e 是矿中的不同元素的无序对的集合y 中的 元素叫做图g 的顶点，y 中元素的个数f v l 叫做图g 的阶，e 中的元素叫做图g 的边，通常用y ( g ) 和e ( g ) 分别表示图g 的顶点集合与边集合对于图g 中的 顶点u 和u ，若边e = “u e ( g ) ，则称u 和u 相邻，和u 互为邻点“和 叫做 e 的端点，分别与e 关联若图g 的边e 和边，有一个公共端点，则称e 和，相 邻具有同一端点的一条边叫作环，具有相同端点的两条边叫作重边没自，莺边与 环的图叫做简单图在图g 中与顶点“相邻的顶点的全体叫做“的邻域，记作 一3 一 、绪论 a r c ( “) ，称j | 3 ( u ) i 为点的度数，记作d g ( 乱) 川d u 】表示 u ) u g ) 如果 图g 的所有顶点度数都等于d ，则称图g 是d 一止则的为方便，将度数为k 的顶 点叫做七一点，度数大于等于k 的顶点叫做七+ 一点度数中最大者和最小者分别 叫做图g 的最大度和最小度，分别记作( g ) 和j ( g ) 度数为0 的点称为孤立点， 度数为1 的点称为悬挂点或叶点，与悬挂点相关联的边叫做悬挂边在不产生混 淆的情况下，把g ( “) 、d g ( u ) 、( g ) 、j ( g ) 分别简记为( u ) 、d ( “) 、a 、6 对于图g = ( v e ) 和图g = ( y 7 ，f ) ，若有矿7 v e ，则称图g 7 是图g 的一个子图进一步，如果g 7 包含所有形如m y e ( g ) ，o ，y v 7 的 边，则称g 7 为g 的一个导出子图，并记作g = a v ，1 用玩表示图g 的所有 最大度顶点组成的集合，则g 玩】表示由所有最大度顶点导出的图g 的子图， e ( g 【v a 】) 一 e l e 一伽e ( g ) ，“，口仫) 于足e ( g 【虼】) = 0 即表示g 中没有 两个相邻的最大度顶点，而e ( g 仫】) o 表示g 中存在相邻的最大度顶点称图 h = ( v u v 7 ，e u e 7 ) 为图g 与g ，的并，记作g u g 对于矿y ( g ) ，从g 中删 去y 7 中项点及与y 7 中的顶点相关联的边后得到的图记作a i r v 7 】或g 一； 对于“，u y ( g ) ，ge ( g ) ，在g 中连接点“，t ，后得到的图记作g + u u 若 y y 中的任何两个顶点都不相邻，则称y 为图g 的一个点独立集若曰 中的任何两条边都不相邻，则称为g 的一个边独立集或匹配若g 的一个匹 配e 7 包含g 的所有顶点，则称为完美匹配 若v = = o l ，z 2 ，2 k - - i ，e = = z o z l ，2 l x 2 ；，z 七一2 。一1 ) ，贝u 称图p = ( v 曰) 为一条路，其中z l ，z k l 叫做路p 的端点，p 的边数叫做p 的长度称图 c = 尸+ f o o z k 一1 1 为一个长为k 的圈，又简称为后一圈若对图g 的任意两个顶 点，z ，y y ( g ) ，g 中都有一条路连接它们，则称g 是连通的g 中最短的z y 路的长度叫做顶点z y 之间的距离若从连通图g 中任意删去k 1 个点后g 仍连通，则称图g 是七一连通的对于xcy ( g ) ，若g x 不连通，则称x 是g 的一个点割，当g 一 z ) 不连通，点2 称为g 的一个割点不含圈的图叫做森林； 连通的无圈图叫做树对于扎+ 1 阶的图f ，若y ( f ) = z o ，o l ，z 。) ，e ( f ) = o 茁1 ，茁o z 2 ，茁o 。住；z l z 2 ，霉2 2 3 ，z n l z n ) ，见u 称f 为n 阶扇 对于图g = ( v e ) ，若y 中任何两个顶点都相邻，则称g 是完全图或团若 y 可剖分成r 个类，k ，- 一，k ，其中r 是一个大于等于2 的正整数，使得k 是 g 的独立集，则称g 为r 一部图若r 一部图的每个顶点与其所在部以外的点都相 邻，则称g 为完全r 一部图 若能将图g 画在平面上，使得它的边仅在端点处相交，则称g 是一个可平面 一4 一 、绪论 化图，图g 在平面上的一个嵌入叫做平面图g 7 g 的边将平面剖分成的若干个 单连通区域的闭包叫做g 7 的面，常用f ( c ) 表示图g 的面集合连通平面图g 有欧拉公式i v ( c ) i i e ( c ) i + i f ( g ) i = 2 在后面的讨论中，用 s i 表示集合s 中的元素个数，崩扛1 和i o 分别表示 不小于z 的最小整数和不大于z 的最大整数在图中，川实心点表示度数确定的 点用空心点表示度数不确定的点 本学位论文所用的符号和术语基本上与文献【l 】一致 ( - - - ) 、本文的主要结果 本学位论文主要围绕上面的猜想，对一些图类进行研究，验证该猜想 论文的第二部分讨论的是一些特殊图，验证了几个特殊图类的邻点可区别全 色数满足猜想。并证明了非轮的h a l i n 图的邻点町区别全色数 在第三部分，进一步讨论广义p e t e r s e n 图，得到了以下结果： 当n 一0 ( r o o d 2 ) 且k 一0 ( m o c l 2 ) 或者n = 0 ( m o d 2 ) ，k ；l ( m o d 2 ) 且k = n 2 或者n = l ( m o d 2 ) ，n = p t ，k = 驴( t ，p 3 ，5 ，7 ，) ，q 1 ，2 ，3 ，) ，p g ) 时， 正整数，k ) 不构成广义p e t e r s e n 图；对于其它的( n ，七) ，有x m ( 尸( n ，七) ) = 5 最后研究的是两类含有特定圈的图的邻点可区别全染色，并得到了它们的精 确的邻点可区别全色数 一5 二、儿类特殊图的邻点可l 别全染色 二、几类特殊图的邻点可区别全染色 本章主要考虑一些特殊图的邻点可区别全染色问题给出了它们的邻点可区 别全色数的确切值或者它们的上、下界 ( 一) 、几个特殊图类的邻点可区别全染色 引理2 1 【1 4 】设图g 是一个有i e ( g ) l 条边，i y ( g ) 1 个顶点的幽若i e ( g ) l ( g ) 【w ( g ) i z j ，则g 是第二类的 引理2 2 【”】若图g 所有的最大度顶点导出的了图是一个森林，则) ( 7 ( g ) = ( g ) 引理2 3 对于任意图g ，有x t ( g ) x t ( g ) y ( g ) + x 7 ( g ) 证明：根据正常伞染色的概念，相邻顶点的颜色集合h 丁以相同，再根据邻点 可区别全染色的定义，显然有x r ( c ) x 。t ( g ) 根据图g 的正常点、边染 色的定义可知，相邻顶点的染色以及其相邻边的染色都必须不同，所以当用 g l = 1 ，2 ，一，x ( g ) ，c 2 = x ( g ) + 1 ，x ( g ) + 2 ，一，x ( g ) + x 7 ( g ) 两个颜色 集合分别给g 进行正常点、边染色时，得到的是图g 的正常全染色，并且对于 任意两个邻点t ，口y ( g ) ，u v e ( g ) ，必定有c ( t ) e ( ) ，根据邻点可区别 全染色的定义，这个正常全染色也是图g 的一个( x ( c ) + x 7 ( g ) ) - - a v d t c 于是 x 。t ( g ) ) ( ( g ) + x 7 ( g ) 引理证毕 口 定理2 1 设蟛表示各部阶数均为s 的r 部完全图，记= ( k ；) 当r s = 0 ( r o o d 2 ) 时，有x 。t ( k ；) 一a + 2 ；当r s l ( m o d 2 ) 时，有+ 2 x m ( 蟛) + 3 证明：当5 = 1 ，研为r 阶完全图，根据定理i 6 宵 ( 叫： 越) + 2 一_ 0 北) ； 【a ( k 7 ) + 3 ，r l ( m o d 2 ) 当r = 2 ，霹为( 霹) = 8 的完全：二部图，文献 1 】己得到x a t ( 研) = s + 2 所以下面只考虑r 3 ，8 2 的情况 一6 一 二、儿类特殊图的邻点可区别全染色 由于孵中有相邻的最大度顶点，所以根据定理1 4 ，有y 。t ( 蜓) + 2 = s ( r 一1 ) 当r 8 = 0 ( r o o d 2 ) 时，下面仅需证明蟛存在一个( 一2 ) 一a v d t c 当r = 0 ( r o o d 2 ) ，令r = 2 t ( t = 2 ，3 ，) ，如下定义从v ( f f ；) ue ( 霹) 纠颜色 集合 l ，2 ，2 t + 1 ) 的映射，： ，( y ( r 1 ) ) = t ，i 一1 ，2 ，2 t ； ，( m ( n ，r 2 ”1 一 ) ) = 2 t + 1 ，i 一1 ，2 ，- 一，； ，( 彳( n ，r 2 h 3 一。) ) 一1 ，t = 3 ，4 ，t + 1 ； f ( m ( r l ，如) ) 一，( a 彳( n ，r 2 * 5 一1 ) ) = 2 ， i 一5 ，6 ，t + 2 ； f ( m ( r 2 ，r 4 ) ) = f ( m ( r l ，r 5 ) ) = ，( m ( n ，r 2 t + 7 一 ) ) = 3 ，i = 7 ，8 ，t + 3 ； f ( m ( r t 一1 ，r t + 1 ) ) 一，( a f ( n 一2 ，r e + 2 ) ) = 一f ( m ( r 2 ，r 2 t 一2 ) ) 一f ( m ( r l ，r 2 t 一1 ) ) = t ： ，( 朋( ，吒+ 2 ) ) 一，( 彳( 一i ，r t + 3 ) ) = t ，- = ，( ( 岛，您一1 ) ) = ，( 且彳( 您，您。) ) = t + 1 ： y ( m ( r 2 t 一2 ，r 2 t ) ) = f ( m ( r 2 t 一3 一i ，n ) ) 一2 t 一1 ，t = 1 ，2 ，一，t 一2 ； ，( 彳( r 一1 一 ，r t ) ) 一2 t ， t = 1 ，2 ， 1 其中y ) 表示部r 中的所有顶点，m 帆，r j ) 表示部允，q 间的任意一个完 美匹配 经过上面，的染色，砰。中各顶点均有一( 2 t 一1 ) 一( 2 t 一1 ) ( s 一1 ) 条关联 边未染色只考虑砰的任意两个部问未染色的边，易见这是一个( 5 1 ) - - i l ：n 二部图根据二部图的边色数等于其最大度，可将 的任意两个部间所有未染 色的边用( s 1 ) 种颜色正常染色所以j 皆的所有未染色的边u 丁用( 2 t 1 ) ( s 一1 ) 种颜色正常染色这样，我们就得到了x 的一个( 2 t 一1 ) s - b2 一a + 2 一正常 全染色根据整个染色过程，显然有：- c ( y ( r 2 。) ) = i ) ，u ( v ( r 2 i - - i ) ) = t + i “一 1 ，2 ，t ) ，即相邻丁贞点的颜色集合不会相同根据定义a ，知，这是砰。的一个 ( + 2 ) - - a v d t c 当r = l ( m o d 2 ) ，令r = 2 t + l ( t = 1 ，2 ，) ，如下定义从y ( 蟛) ue ( 霹) 到 颜色集合 1 ，2 ，4 + 2 ) 的映射，： 一 一 二、儿类特殊图的邻点可l 别全染色 f ( v ( r 。) ) = f ( m ( r i + l ，r 2 t + 。) ) = ，( m ( r t + 2 ，r 2 t + ，一1 ) ) 一= f ( m ( r + ，n + 件1 ) ) = ： f ( m ( r t + 1 ，r 2 t + t ) ) = ，( 彳( n + 2 ，r 2 t “一1 ) ) 一- = f ( m ( r “，r t + h 1 ) ) = 2 t + i + 1 其中i = 1 ，2 ，2 t + 1 ，当m 2 t + 1 时，表示，1 n 2 t + 1 且 m = n ( m o d ( 2 t + 1 ) ) 经过上面，的染色，；”1 中各顶点均有一4 t = 2 t ( s 一2 ) 条关联边未染 色考虑k + 1 中所有未染色的边，易见这是一个2 t ( s 一2 ) 一正则图 当s = 0 ( r o o d 2 ) ，所有未染色的边能分解为2 t ( s 一2 ) 个均含( 2 tq - 1 ) s 2 条边 的独立集，每个边独立集中的所有边町以用一种颜色染，放共需要2 t ( s 一2 1 种颜 色这样，得到k + 1 的一个2 t s + 2 = + 2 正常全染色并且根据整个染色过 程，显然有：召( y h ) ) 一 2 t4 - 14 - 0 = 1 ，2 ，一，2 t + 1 ) ，即相邻顶点有不同的颜 色集合根据定义可知，这是j 鬈t + l ( s = o ( m o d 2 ) ) 的一个( + 2 ) 一a v d t c 当s l ( m o d 2 ) ，则r 8 = l ( m o d 2 ) 经过上面，的染色，不考虑群”1 中 已染色的边，记k ；”1 中未染色的( 2 t + 1 ) ( s 一2 ) s t 条边及所有( 2 t + 1 ) 8 个顶 点构成的子图为k 7 由于l e ( k ，) | a ( k 7 ) l i v ( k 7 ) l 2 j ，于是根据引理2 1 有， x ，( k 7 ) 一a ( k 7 ) + 1 = 2 t ( s 一2 ) + 1 而显然 l ，2 ，4 t + 2 ) 已经不能再用，所 以给k + 1 的这个正常全染色总芡需要4 + 2 + 2 t ( s 一2 ) + 1 = 2 t s + 3 = a 十3 种颜色根据整个染色过程，显然有虿( y ( n ) ) 一 2 t - 1 - 1 - t - i ) ( i = 1 ，2 ，一，2 t + ! ) ， 即相邻顶点的颜色集合都不相同于是根据邻点u ，区别全染色的定义可知，这是 j ”1 0 = l ( m o d 2 ) ) 的一个( + 3 ) - - a v d t c 定理证毕口 根据定理2 1 立即町得定理2 2 定理2 2 若g 为每个部阶数均为s 的r 部七一正则简单图，当r 8 = o ( m o d 2 ) 时， 有x a t ( g ) = a + 2 ；当r s l ( m o d 2 ) 时，有+ 2 x 。t ( g ) + 3 定义2 2d 6 设g 是一个长度为r 的圈，将g 的每一个顶点替换成k 个点的独 立集，并使原本相邻的两个点对应的两个独立集中的点两两相邻，这样得到的图 叫做广义圈，记作g ( ) 定理2 3 对于广义圈o r ( k ) ( r 3 ，k 1 ) ，记a = ( g ( k ) ) ，当r k ；o ( m o d 2 ) 时， 有x a t ( c y r ( ) ) = a + 2 ；当r k = l ( m o d 2 ) 时，有+ 2 x 。t ( g ( k ) ) a + 3 证明：当r = 3 时，g ( ) 为每个部的阶数均为k 的3 部图，即为定理2 1 中的 一8 一 二、几类特殊图的邻点可l x 别全染色 k z ，故定理结论已证冈为g ( k ) 自相邻的两个最大度顶点，根据定理1 4 有： y 。( g ( ) ) a + 2 ，其中a = 2 k 下面考虑足r 4 的情况 当r 一0 ( r o o d 2 ) ，令r 一2 t ( t 一2 ，3 ，) 由于o ( 舢的任意两个相邻顶点 的部构成一个完全二部图，故町如下定义从y ( g 女 ) u 昱( g ) ) 到颜色集合 1 ，2 ，- ，2 七+ 2 ) 的映射，： ，( y ( r 2 ，1 ) ) 一1 ，t = 1 ，2 ，t ； ，( y ( r 2 。) ) = 2 ，i = 1 ，2 ，一， f ( e ( r 2 ；一l ，r 2 i ) ) ， 3 ，4 ，k + 2 ， 一1 ，2 ，t ； f ( e ( r 2 j ，r 2 3 + 1 ) ) 一 七+ 3 ，k + 4 ，一，2 南+ 2 ) ， j 一1 ，2 ，一，t l ； f ( e ( r l ，r 2 ) ) ， 七+ 3 ，k + 4 ，2 七十2 ) ， j = 1 ，2 ，- ，t 一1 其中y ( n ) 表示部n 中的所有顶点，e ，巧) 表示部n ，q 之间的所有 边根据整个染色过程可知，是g ( k ) 的一个( + 2 ) - - 正常全染色，并且 虿( 矿( r 。t 一。) ) = 2 ，虿( y ( 您t ) ) 一 1 1 ( i = 1 ，2 ，一，t ) ，于是相邻顶点的颜色集合 均不相同所以，是g ( ) ( r = 0 ( r o o d 2 ) ) 的一个( + 2 ) - - a v d t c 当r = l ( m o d 2 ) ，令r = 2 t + l ( t = 2 ，3 ，) ，如下定义从y ( g ( ) ) ue ( g ( k ) ) 到颜色集合 1 ，2 ，3 ，4 ) 的映射，： ，( 1 厂( r 1 ) ) = = f ( m ( r 2 i + 1 ，r 2 。+ 2 ) ) 一1 ， i 一1 ，2 ，t 一1 ； ，( y ( 他。) ) = ，( l 彳( r l ，r 2 t + 1 ) ) = 2 i = 1 ，2 ，t ； ，( y ( r 2 件1 ) ) = ，( m ( r 1 ，r 2 ) ) = 3 ，i 一1 ，2 ，t ； y ( m ( r 2 ，+ 1 ) ) = 4 ， = 1 ，2 ，一，t 其中y ( r t ) 表示部n 中的所有顶点，m ( r t ，r 3 ) 表示部n ，r j 之间的任意一个 完美匹配经过上面，的染色，g 中箨个顶点均有2 k 一2 条关联边未着色只 考虑聊“1 中所有未染色的边，易见这是一个( 2 七一2 ) 一正则图 当七一0 ( r o o d 2 ) ，易见这磐边能分解为2 k 一2 个均含k r 2 条边的独立集， 每个边独立集中的所有边都可以崩一种颜色染，故共需要2 k 一2 种颜色，不妨 设为 5 ，6 ，2 七+ 2 ) 至此，已得到g ( k ) 的一个( 2 七+ 2 ) 一正常全染色并且 虿( y ( r 1 ) ) 一 4 ，召( y ( r 2 ) ) = 虿( y ( r r ) ) = 1 ) ，虿( y ( r 2 t 一1 ) ) = 2 ) ，虿( y ( r 2 d ) 一 3 ) ( = 2 ，3 ，) ，即相邻顶点的颜色集合均不相同所以这是g ( k ) ( 后= 0 ( m o d 2 ) ) 的一个( + 2 ) - - a v d t c 当k = l ( m o d 2 ) ，则r k = l ( m o d 2 ) 经过上面，的染色，不考虑g ( 1 中已 一9 一 二、儿类特殊图的邻点可l x 别全染色 染色的边，记g 中未染色的r k ( k 一1 ) 条边以及所有r 七个顶点构成的。j 二图 为c 由于i e ( c 川 a ( c 7 ) l l v ( c ) l 2 j = ( 2 k 一2 ) 【r k 2 j ，于是根据引理2 1 有 ( e 7 ) = a ( c 7 ) + 1 = 2 k 一1 而颜色1 ，2 ，3 ，4 显然都已不能再用，所以给g 的 这个正常全染色总共需要+ 3 种颜色根据上面的染色过程可知，虿( y ( r 1 ) ) = 4 1 ，虿( y ( r 2 ) ) = 虿( y ( n ) ) = 1 ，虿( y ( 您。1 ) ) = 1 2 ，虿( y ( r a ) ) = 3 ) 一 2 ，3 ，一，t ) ，即相邻顶点的颜色集合均不相同所以这是g ( 詹= l ( m o d 2 ) ) 的一 个( + 3 ) - - a v d t c 定理证毕口 定义2 3 发g 是一个简单图，把( g ) 叫做图g 的广义m y c i e l s k i 图，如果 y ( 们二( g ) ) = v o l ，v f f 2 ，一，2 怖；u 1 1 ，u 1 2 ， = e ( g ) u ”( 件1 ) i 嘞铷e ( g ) ，1 v ( g ) 一 v o d i = 0 ，1 ，一，p ) ，口l p ；l ，2 ，p ；) ；e ( ( g ) ) j ，k p ，i 一0 ，1 ，- ，n 1 ) ，其中 例如当图g = 甄一 e ，佗= 3 时，m 3 ( k 4 一 e ) 为下图： m 3 ( 甄一 e ) ) v 3 1 u 3 2 3 3 v 3 4 定理2 4 对任意的简单图g ，有2 ( g ) + 1 ) ( 。t ( 尬。( g ) ) ) c a t ( g ) + ( g ) 证明：显然对任意的简单图g ，根据尬；( g ) 的定义，有( m n ( g ) ) = 2 a ( a ) ，从 - 而x “( 霸( g ) ) ( 尬。( g ) - 4 - 1 2 a ( g ) + 1 设映射，为g 的一个从v ( g ) u e ( g ) 到颜色集合 1 ，2 ，x 。( g ) ) 的 一个邻点口，区别全染色设g 也是一个映射根据( g ) 的定义，有g e ( ( g ) ( t 8 ，i ，s 1 ，2 ，n ) ，j 一1 ，2 ，一，p ) ，t 勺t h 缸e ( l 霸( g ) “ 1 ，2 ，n ，1 j ，k p ) ，所以可以定义 g ( v 1 1 ) 一，( ”) ，i = 1 ，2 ，礼，j = 1 ，2 ，一，p ； 一1 0 一 二、儿类特殊图的邻点可k 别全染色 夕( 2 b + 1 ，i ) = ，( t j 0 ，t ，o ) ， = l ( m o d 2 ) ，j k ，j ，k 1 ，2 ，一，p ) ； 记k = m i ，v i 2 ，) ，则e ( k ) = 毋( 0 n 下面取i 一0 ( r o o d 2 ) ( 2 n ) 根据图慨( g ) 的定义，k ，k + 1 及其它们之间的边构成一个 最大度为a ( g ) 的二部图因为二部图的边色数等于其最大度，所以可令 9 ( e ( k ，k + 1 ) ) 一 灭。t ( g ) + 1 ，x 。t ( g ) + 2 ，一，x “( g ) + ( g ) ) 显然g 是肘二( g ) 的 一个y 。t ( g ) + ( g ) 一正常全染色，并且根据整个染色过程可知，g 也是 霸( g ) 的 一个( x 。t ( g ) + ( g ) ) - - a v d t c 定理证毕 口 定义2 4 定义简单图g 和日的笛卡儿乘积图g h ，v ( a h ) 一v ( a ) y ( 日) ，( “，口) 和( 7 ，t ，7 ) 相邻当且仅当“一u 7 且 t ，7 e ( h ) 或口一口且 e ( 日) 设c = 。l 。2 ；。1 和c k = y 1 耽y , , y l 是两个点不交的圈，其中m ，n 3 则y ( c kxc k ) 为 u f ，= ( 瓤，y a ( i = 1 ，2 ，一，m jj 一1 ，2 ，- ，n ) ， e ( c k c k ) = u t ，l u , ，2 ，啦，2 ，3 ，一，饥，肛1 饥川m t t ，1 ，e = 1 ，2 ，一，m ； t 正1 。“2 j ，u 2 , j u s d ，t m 一1 d “m ，j ，钍m j “l j ，j = 1 ，2 ，n ) 如下图： c m “ 定理2 5 若m 3 ，n 3 是整数，记g ：c kxg ，有t ( g ) = 6 证明：因为当m ，n 3 时，图g 有相邻的最大度顶点，且a ( g ) = 4 ，所以根据定 理1 4 有x 。t ( g ) ( g ) + 2 = 6 当m = 0 ( r o o d 2 ) ，佗一0 ( r o o d 2 ) 时，下面定义一个从v ( a ) ue ( g ) 到颜色集 合 l ，2 ，- ，6 ) 的映射厂： ，( “。j ) = 1 ，i - 4 - j 一0 ( m o d 2 ) ，1 i m ，1 j n ； 一l l 一 二、儿类特殊图的邻点可【x 别全染色 ，( u ) = 2 ， + j = 1 ( r o o d 2 ) ，1 i m ，1 j n ； ，( u l ，j “t ，j + 1 ) 一3 ， 一1 ，2 ， l ，j 一1 ( r o o d 2 ) ，1 j n ； ，( “k l u ) = ，( u j v 4 , j + 1 ) 一4 ， = 1 ，2 ，一，m ，j = 0 ( r o o d 2 ) ，2 j 喵 ，( u ；j u i + l j ) = 5 ， t = 1 ，2 ，m ，j = 1 ( r o o d 2 ) ，1 j n ； 。，( u t l u n i ) = y ( u i j u + l d ) = 6 ， i l ，2 ，m ，歹= 0 ( r o o d 2 ) ，2 j n + 3 时，点是唯一的最大度顶点，根据引理2 2 ，有x ( f m v 最) = 先用个颜色给r v r 的所有边正常染色，然后用第+ 1 个颜色给点w 染 色，并将所有边t l 仇1 ( 一2 ，3 ，m 一1 ) 上的颜色都改染为第+ 1 个颜色，此 时所有剩余顶点的关联边的颜色集合中都至多包含一1 个颜色而且度相等的 顶点导出的子图足点独立集、路或是路的并，所以很容易给这些顶点正常染色， 并使得相邻顶点的颜色集合不同从而得到j m v r 的一个( + 1 ) - - a v d t c 当m 4 - 3 时，显然图f m v r 青相邻的两个最大度顶点，根据定理1 4 有 x m ( j k v r ) + 2 故下面只要证明f m v r 存在一个( + 2 ) - - a v d t c e p u 当m n 4 - 3 时，点 ，“2 ，“3 ，u 。一l 均足最大度顶点先用+ 1 个颜色 给，m v r 的所有的边进行正常染色，再将点 片j 它的关联边的颜色集合中所缺 少的颜色染，并把所有边u 。饥l “= 2 ，m 一1 ) 上的颜色都改染为第+ 2 个颜 色此时除点w 外所有顶点的关联边的颜色集合中都至少缺少2 个颜色，而且度 一1 4 一