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

关于图的点可区别染色问题 摘要 图的染色理论是图论研究的重要理论之一近几年来，各类染色问题也被相 继提出，图的点可区别染色问题以及邻点可区别染色问题是图的染色理论中的 一种推广本文主要研究了图的点可区别边染色及邻点可区别全染色问题 论文分为三章，在第一章中主要是对本学位论文所涉及到的问题、背景、定 义及点可区别染色问题的研究现状进行一个综述 第二章主要研究了一些图的点可区别边染色的问题1 9 9 3 年，a c b u r r i s h e 和r h s c h e l p 提出了图的点可区别边染色的概念和猜想，并得到了一些结果 h a l i n 图一直以来是学者们较为关注的一类图本章主要研究了3 正则h a l i n 图 和a ( c ) 4 的h a l i n 图的点可区别边染色问题，并得到了星、扇、轮等联图即 & v & 、rvr 、v 眠的点可区别均匀边色数 第三章研究了关于图的邻点可区别全染色问题2 0 0 2 年，张忠辅教授根据计 算机科学、信息科学、网络等实际问题，在点可区别边染色的基础上提出了邻 点可区别边染色、邻点可区别全染色的概念和猜想本章主要探讨了( g ) = 7 的2 连通外平面图的邻点可区别全染色问题 关键词：点可区别染色；均匀边染色；全染色；h a l i n l 羽 t h ep r o b l e mo fv e r t e xd i s t i n g u l s h i n g c o l o r i n g o fg r a p h s a b s t r a c t t h ec o l o r i n gt h e o r yo fg r a p hi so n eo ft h ei m p o r t a n tt h e o r yi ng r a p h s r e c e n t l y , m a n yk i n d so fc o l o r i n gp r o b l e m sa r ep r e s e n t e d ，s u c ha st h ev e r t e xd i s t i n g u i s h i n ge d g e c o l o r i n ga n da d j a c e n tv e r t e xd i s t i n g u i s h i n gc o l o r i n ga r ea l lt h ee x t e n s i o no fc o l o r i n g t h e o r y i nt h i sp a p e rw ed e a lw i t hs o m eg r a p h si nv e r t e xd i s t i n g u i s h i n ge d g ec o l o r i n g o ra d ja c e n tv e r t e xd i s t i n g u i s h i n gc o l o r i n gp r o b l e m sb yu s i n gt h ei n d u c t i o nm e t h o d t h i st h e s i sc o n s i s t so ft h r e ec h a p t e r s i nt h ef i r s tc h a p t e r , w ei n t r o d u c es o m e p r o b l e m s 、b a c k g r o u n d sa n dt h ed e f i n i t i o no fv e r t e xd i s t i n g u i s h i n gc o l o r i n g i nt h es e c o n dc h a p t e r , w em a i n l yd e a lw i t i lt h ev e r t e xd i s t i n g u i s h i n ge d g ec o l o r - i n gp r o b l e m i n19 9 3 ，a c b u r r i s h ea n dr h s c h e l pp r e s e n t e dt h en e wd e f i n i t i o na n d c o n j e c t u r eo fv e r t 固ad i s t i n g u i s h i n gc o l o r i n g ，a n do b t a i n e ds o m er e s u l t s i nt h i sc h 印- t e r , w ei n v e s t i g a t et h ev e r t e xd i s t i n g u i s h i n ge d g ec o l o r i n gi n3 - r e g u l a rh a l i ng r a p ha n d h a l i ng r a p hv v i t h ( g ) 4 a l s o ，w eo b t a i nt h ev e r t e xd i s t i n g u i s h i n ge q u i t a b l ee d g e c h r o m a t i cn u m b e ro f & v & 、rvr 、w nv i nt h et h i r dc h a p t e r , w es t u d yt h ea d j a c e n tv e r t e xd i s t i n g u i s h i n gt o t a lc o l o r i n g p r o b l e m b a s e do nt h et h e o r yo f v e r t e xd i s t i n g u i s h i n gc o l o r i n g ，p r o f e s s o rz h a n gz h o n g f u p r e s e n t e d t h en e wd e f i n i t i o na n dc o r l j e c t u r eo fa d j a c e n tv e r t e xd i s t i n g u i s h i n gc o l o r i n g i nt h i sc h a p t e r , w ei n v e s t i g a t et h ea d j a c e n tv e r t e xd 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 o n2 - c o n n e c t e do u t e rp l a n eg r a p hw i t ha ( g ) = 7 k e yw o r d s ：v e r t e xd i s t i n g u i s h i n gc o l o r i n g ；e q u i t a b l ee d g ec o l o r i n g ；t o t a lc o l o r i n g ；h a l i ng r a p h l l 浙江! j 币范大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意本人完全意识到本声明的法律结果由本人 承担 名：象嘴 吼叫年月节日 学位论文使用授权声明 名缘任”魏f 。7 焱午日p 伊 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条例我的学位 论文中凡引用他人已经发表或未发表的成果、数据、观点等，均已明确注明并详 细列出有关文献的名称、作者、年份、刊物名称和出版文献的出版机构、出版 地和版次等内容论文中未注明的内容为本人的研究成果 如有违反，本人接受处罚并承担一切责任 何彳 船似 、，e口 蜘 师 究 聊 教 1 1 有关概念 1绪论 本文所考虑的图g 都是有限、无向、简单图分别用y ( g ) 、e ( g ) 、( g ) 、 d g ( u ) 和( u ) 表示图g 的顶点集、边集、最大度、顶点 的度与和顶点u 相 邻的点的集合在不引起混淆的情况下，分别简记为y 、e 、d ( v ) 和( 口) 在 图g 中与顶点让相邻的顶点的全体叫做u 的邻域，记作n e ( u ) ，称i g ( ) i 为点 乱的度数，记作如( “) 如果图g 的所有顶点度数都等于d 则称图g 是d 正则的 为方便，将度数为k 的顶点叫做七点，度数为0 的点称为孤立点，度数为l 的点称为 悬挂点或叶点，与悬挂点相关联的边叫做悬挂边 对于图g = ( ke ) 和图g = ( v ，e ) ，若有y ke e ，则称图g 是图g 的一个子图进一步，如果g 7 包含所有形如x y e ( g ) ，x ，y v7 的 边，则称g 为g 的一个导出子图，并记作g = a i r 1 用仫表示图g 的所 有最大度顶点组成的集合，则g 【仫l 表示由所有最大度顶点导出的g 的子图， e ( g v a l ) = ele = u v e ( g ) ，u ，u 仫) 于是e ( g 【坛1 ) = d 表示g 中没有两 个相邻的最大度顶点，e ( a v a 】) d 即表示g 中有两个相邻的最大度顶点 称图h = ( v uv ，eue ) 为图g 与g 7 的并，记作gug 对于y y ( g ) ， 从g 中删去y 中顶点及与其中的顶点相关联的边后得到的图记作g 【y y l 或g y7 ；对于u ，u y ( g ) ，u u e ( g ) ，在g 中连接点u ，u 后得到的图记作 g + 仳口 若y y 中的任何两个顶点都不相邻，则称y 为图g 的一个点独立 集若e e 中的任何两条边都不相邻、则称e 为g 的一个边独立集或匹配 若g 的一个匹配e 包含g 的所有顶点，则称e 为完美匹配 若从连通图g 中任意删去七一1 个点后g 仍连通，则称图g 是七连 通的对于x y ( g ) ，若g x 不连通，则称x 是g 的一个点割集，当 l l 绪论 g 一 z ) 不连通，点x 称为g 的一个割点不含圈的图叫做森林；连通的 无圈图叫做树对于佗+ 1 阶的图s ，若v ( s ) = x o ，x l ，z n ) ，e ( s ) = x o x l ，x o x 2 ，x o x 。) ，则称s 为礼阶星，记为岛对于佗+ 1 阶的图f ，若 v ( p ) = z o ，x l ，x 。 ，e ( r ) = x o x l ，x o x 2 ，x o x t l ；x l x 2 ，x 2 x 3 ，x n - 1 x n ， 则称f 为佗阶扇，记为r 对于礼+ l 阶的图w ，若v ( w ) = 执，x l ，z 。 ， e ( w ) = x o x l ，x o x 2 ，z o z 。；x l x 2 ，x 2 x 3 ，x n - l x 他，x n x l ，则称为t i 阶轮， 记为帆 对于图g = ( k e ) ，若y 中任何两个顶点都相邻，则称g 是完全图或团若 y 可剖分成r 个类，w ，其中r 是一个大于等于2 的正整数，使得k 是 g 的独立集，则称g 为r 部图若卜部图的每个顶点与其所在部以外的点都相邻， 则称g 为完全r 部图 若能将图g 嵌入在一个平面上，使得它的边仅在端点处相交，则称g 是一个 可平面化图，图g 在平面上的一个嵌入叫做平面图g 文中未加说明的术语和记 号可参见文【4 】 1 。2 关于图的点可区别染色研究综述 图论在现代科学技术中有着广泛的应用，如：社会学、计算机科学、信 息科学、密码学、d n a 的基因谱的确定和计数、工业生产和企业管理中 的优化方法等都广泛地应用了图论及其算法关于图的染色问题，是图论 研究的主要内容之一，并且近年来图的染色问题得到了广泛的研究和应 用，新概念、新方法不断的出现，是当前非常活跃的学科问题1 而图的点 可区别染色问题是众多类型中用不同方式对图进行标号的一个特殊问题 1 9 9 3 年a c b u r r i s h e 和r h s c h e l p 提出了图的点可区别边染色的概念和猜想此 后包括a c b u m s h e 在内，r h s c h e l p ，p n b a l i s t e r , b b o l l o d s 等人在文献闭中做了 进步的探讨2 0 0 2 年，张忠辅教授【3j 根据计算机科学、信息科学、网络等实际 问题，在点可区别边染色的基础上提出了邻点可区别边染色、邻点可区别全染色 2 l 绪论 的概念和猜想本文所考虑的图均为连通、有限、无向的简单图 对于给定的简单图g 和正整数k ，若存在映射厂：e ( g ) 一 1 ，2 ，3 ，七 满足任意相邻的边e ，e 有f ( e ) f ( e ) ，则称，为g 的一个正常边染色，简记为 k p e co fg 且称 x7 ( g ) = m i n kik p e co fg 为g 的边色数【4 1 若，是g 的一个k p e c ，且满足v u ，u y ( g ) ，u u ，其中c ( u ) c ( v ) ， 则称，为g 的点可区别边染色，简记为k v d e co fg ，而 x 0 ( g ) = m i n kl k v d e co fg ， 称为g 的点可区别边色数f5 1 ，其中 c ( u ) = f ( u v ) iu y e ( g ) 对简单图g ，6 ( g ) ，a ( a ) 分别是g 的最小度和最大度，扎i 表示g 中度数为i 的点数，( 二) 表示n 个中取m 个的组合数，则称 肛e g ，= m a x t m t n t zi ( ：) 扎i ，6 c g ，t c g ， 为g 的组合度 6 1 由组合度及点可区别边染色定义，不难得到 x 幺( g ) 肛( g ) 3 ( 1 1 ) 1 绪论 设厂是g 的一个k v d e c ，且满足 e i l l 马i f 1 则称，为g 的点可区别均匀边染色，简记为七一v d e e co fg ，而称 x 赢( g ) = m i n ki 七一v d e e co fg ) 为g 的点可区别均匀边色数【6 1 ，其中 e i = eif ( e ) = 啦 为解决网络权的分配等问题，b u m s 、b a z g a n 等人先后提出点可区别边染色 问题，得n t 相应的结果，在有关结论的前提下提如下猜想 猜想1 1 7 1 对于i v ( g ) i 3 的连通图g ，有 u ( o ) x 幺( g ) u ( c ) + 1 张忠辅等人得到了一些联图的点可区别均匀边色数，并且在此基础上提出了 以下猜想 猜想2 1 3 1 对l v ( a ) l 3 的简单图g ，有 ( 1 ) 肛( g ) x 幺( g ) 肛( g ) + l ； ( 2 ) x 巍( g ) = x t ( g ) 设g ( ke ) 是阶数至少为2 的简单连通图，k 为正整数，是v ( c ) ue ( c ) 到 1 ，2 ，七) 的映射，对任意u v ( a ) i d c i ( u ) = ，( u ) u f ( u v ) lu u e ( g ) 如果满足 ( 1 ) 对任意u u ，v w e ( g ) ，“叫有，( “u ) f ( v w ) 4 1 绪论 ( 2 ) 对任意姐u e ( a ) 有，( u ) ，( ) ，( 札) ，( u u ) ，( u ) f ( u v ) ，则称 厂为 g 的k 正常全染色进一步，如果还满足 ( 3 ) 对任意乱钉e ( g ) ，有qu ) q ( u ) ，那么称，为g 的七一邻点可区别全染 色，简记为k a v d t c ，称 x 。t ( g ) = m i n klk a v d t co fg 为g 的邻点可区别全色数| 8 】 张忠辅等人研究了路、圈、完全图、完全二部图、星、扇和轮的邻点可区 别全染色，得到了相应图的邻点可区别全色数，并根据对这些图的研究结果，提出 了以下猜想 猜想3 1 8 】 对阶数不小于2 的连通图g ，有x 。( g ) 5z x ( c ) + 3 围绕以上的猜想，许多学者对点可区别染色问题做了一系列的探讨和研究， 得到了以下一些结论 定理1 1 9 1 若图g 是k 可染的且无孤立边，则有x ：( g ) ( g ) + o ( 1 0 9k ) ； 定理1 2 【1 0 1若扎阶图g 是无孤立边且至多有一个孤立点，则有x 幺( g ) s 定理1 3 【l l l 1 2 1 对n 2 ，有x ( rvr ) ： n + 3 ，2 他6 ； l 礼+ 4 ，礼7 对礼3 ，有x k c rvc k ，= 三+ 4 ，n n = 4 6 ； 对扎3 ，有x ：，d e ( gvg ) = 扎+ 4 ； 对几23 ，cx ；如( rvg ) = 3 t = 八i 氍 n 5 l 轨 ，-lj-i_一， 1 绪论 定理1 41 8 对任意的简单图g ，有x 以( g ) a ( c ) + l ；若图g 有两个相 邻最大度点，则x t ( c ) a ( c ) + 2 ；若g 有k 个连通分支g 1 ，g 2 ，g 詹，且 i y ( g i ) l 2 ( i = 1 ，2 ，七) ，则有x t ( o ) = m a x x n ( g 1 ) ，x 。t ( g 2 ) ，x 。( g 七) ； r 设表示礼阶完全图m 3 ) ，则有x 。( ) ： 礼+ 1 扎= o ( r o o d 2 ) ； 【卅2 ，n = l ( m o d 2 ) 除此之外，还有以下一些结果： ( 1 ) 0 3 1 若g 是最大度为3 的简单图，则有x n ( g ) s6 r ( 2 ) 1 11 1 1 1 4 1 令g 是一个圈g ，则有x 口( g ) ： 4 扎= 3 ； 【5 ，扎4 若a ( c ) = 3 ，则有x 。t ( g ) = 5 ； r 若( g ) _ 4 则有( g ) ： 5 以g 蹦) - 眈 【6 ，e ( c i v i l ) o ， 若( g ) _ 5 ，则有( 卟 6 邝( g 盼1 ) 划； 【7 ，e ( c i v i l ) o ， ( 3 ) 1 5 1 设g 是( g ) ：6 的2 - 连通夕卜平面图，贝 j 有x “g ) ： 7 瑚( g 盼| ) 划； i 8 ，e ( g 【仫】) o 6 2 图的点可区别边染色 2 1h a l i n 图的点可区别边染色 本节考虑h a l i n 图假设g 是一个3 连通平面图，如果将其外面r 边界上所 有的边删去后( 蜀上所有顶点的度为3 ) ，g 得到一棵生成树t ，则称g 是一个 h a i n 图f o 成为g 的外面( 其它的成为内面) ，v ( 娲) 成为外面上的点，也叫外点 ( 其余的统称为内点) 若g 是一个点集合为y ( g ) ，边集合为e ( g ) 的h a l i n 图令，是g 的一 个边染色，且c tv ) = ，( u u ) iu u e ( g ) 记为与点可关联的边所染的颜色 集合，记t d = 礼d ( g ) 为g 中点度为d 的点的个数，其中t f ( g ) d ( g ) ，用 n o ( c ) = i v ( f o ) f 记为外点的个数过去，许多学者研究了h a l i n 图的边染色【1 6 l ， 列表染色【l7 1 ，近年来有一些学者开始考虑h a l i n 图的邻点可区别边染色【l8 1 引理2 1 1 9 1g 是一个3 正则h a l i n 图且g w 3 ，那么g 包含结构n 或b ( 如 图2 1 ) ，2 图2 1 引理2 2 1 9 l 图g 是一个h a l i n 图，一1 是阶为p 的轮，则有 ( f ) 外面上的顶点的度数均为3 ；并且任意两个面至多只有一条公共边 ( i i ) 若g 箬一1 ，那么g 中至少有两个内点；且总是存在一个内点删，使得它 仅与一个内点相邻； 7 2 图的点可区别边染色 ( i i i ) 若g 喾一1 ，叫是( i ) 中的一个项点，设n ( w ) = 札，v l ，u 2 ， ，其中 u 是唯一的一个与w 相邻的内点，u l ，v 2 ，v 知是与叫相邻的外点，且x 是与y l 相邻的外点，x o ，z 1 是x 其余的两个邻点；y 是与讯相邻的外点，y o ，y l 是其余的 两个邻点考虑 h 1 = g 一 1 ，v 2 ，v k + z 叫，可叫 ； h 2 = g 一 仉，可件l ，吩 + u 一1 + 1 ) ，2 i j 6 根据数学归纳，任意一个 6 n o ( h ) n o ( a ) 的3 一正则h a l i n 图h 有一个n o ( h ) v d e c ， 由引理2 2 得，g 包含图2 1 所示的结构a 或b ( a ) 若g 含结构a ，假设u l ，“1 ，u 5 ，u 3 ，t j 3 都是g 中的外点( 否则可以取出有此 特征的一组点) 令 h = g u l ，u s + y l u 4 ，u 3 u 4 显然，v l ，“3 ，u 4 都在日的外面上，并且日是一个3 正则h a l i n 图，n o ( 日) = n o ( o ) - a ，因此日有一个( n o ( a ) 一1 ) - v d e c ，记色集为c = 1 ，2 ，3 ，孔o ( g ) 一 l 不失一般性，设 f ( 3 1 l z 4 ) = 1 ，f ( u 3 u 4 ) = 2 ，f ( u 2 u 4 ) = 3 9 区 2 图的点可区别边染色 若未说明，假设g 中边的颜色与日中所对应的边的颜色一致下面我们利用 一个新的颜色n o ( c ) 来完成对g 中的边的染色首先，令9 ( v l u l ) = 1 ，g ( u 3 u 5 ) = 2 ，g ( u l u 4 ) = 3 其次，令g ( u 2 1 2 4 ) = 夕( u l u 5 ) = n o ( c ) 最后，分三种情况对边u 4 u 5 进行染色 情况1f ( u 2 u 3 1 = 1 根据点可区别边染色的定义可知f ( u 3 v 3 ) 隹q ( “4 ) ，设f ( u 3 v 3 ) = 口( 口簪 l ，2 ，3 ) ) ，令g ( u 4 u 5 ) = o t ，则此时的夕是g 的一个n o ( g ) 一v d e c 情况2f ( u 2 u 3 ) 1 但f ( u 3 v 3 ) = 1 显然可知，f ( u 2 u 3 ) 垡q ( “4 ) ，不妨设f ( u 2 u 3 ) = p ( 口聋 1 ，2 ，3 ) 若f ( u 2 v 2 ) 2 ，可设g ( u 4 u 5 ) = p 否则，重染g ( u ：u 3 ) = 3 ，令g ( u 4 u 5 ) = p 因此任意两个不同 的点含有不同的色集合 情况3f ( u 2 u 3 ) 1 且f ( u 3 v 3 ) 1 因为f ( u 2 u 3 ) 岳c f ( u 4 ) ，f ( u 3 v 3 ) 隹 1 ，2 ，f ( u 2 u 3 ) ，令f ( u 2 u 3 ) = ，y ( ，y 簪 l ，2 ，3 ) ) 若，( u 3 1 ) 3 ) = 3 ，显然，f ( u 2 v 2 ) 2 ，则可令f ( u 4 u 5 ) = 7 若y ( , 吐3 v 3 ) 3 ， 不失一般性，设，( 蝴忱) = q ( a 隹 1 ，2 ，3 ，y ) ，再令g ( u 4 u 5 ) = o t ( b ) 若g 包含结构b ，假设钉l ，u 1 ，u 6 ，u 7 ，1 1 3 是g 外面上的点令 h = g 一 “1 ，讹 + v l u 4 ，u 4 u t 那么u 1 ，批，u 7 是日外面上的点，则日是一个3 一正则h a l i n 图，且珊( h ) = n o ( g ) - 1 ，因此日有一个( n o ( c ) 一1 ) - v d e cf ，令色集合为c = 1 ，2 ，3 ，n o ( c ) 一1 不妨设 f ( y l u 4 ) = 1 ，厂( u 4 让7 ) = 2 ，f ( u ：u 4 ) = 3 若未说明，假设g 中边的颜色与日中所对应的边的颜色一致类似地，下面我们 利用一个新的颜色n o ( c ) 来完成对g 中的边的染色先令g ( v l u l ) = 1 ，g ( u 6 u 7 ) = 1 0 2 图的点可区别边染色 2 ，g ( u 1 u 4 ) = 3 ，然后设9 ( u l u 6 ) = g ( u 2 u 4 ) = n o ( v ) 最后，边u 4 u 6 的染法如下 若2 隹 f ( u 2 v 2 ) ，( u 2 u 5 ) ，则令9 ( u 4 u 6 ) = 。，x ，( 乱2 u 2 ) ：f ( u 2 u s ) 1 若2 ，( u 2 可2 ) ，厂( u 2 u 5 ) ) ，由于i c i 6 ，则可令g ( u 4 u 6 ) = x ，z c 1 ，3 ，n o ( g ) ，( u 2 u 2 ) ，( 牡2 u 5 ) ) 因此，9 是g 的一个点可区别边染色，故有 x 0 ( g ) n o ( g ) 定理2 2 若g 是一个h a l i n 图且a ( g ) 24 ，则x 0 ( g ) sn o ( g ) 证明若g = 则由引理2 3 ，有x i ( c ) n o ( c ) 若g 喾，对n o ( g ) 进行数学归纳 若n o ( g ) = 5 ，因为g 是一个h a l i n 图，所以当删去r 上所有边时，g 得到一棵 生成树t ，有n t ( t ) = n o ( g ) = 5 因为 a ( t ) i 1 , 1 ( t ) = ( d 一2 ) r i d ( t ) + 2 d - - - 3 则n 3 ( t ) = m ( t ) = 1 ，扎d ( t ) = 0 ，d 5 ，此时满足条件的图只有一个，易得 x ：( g ) = 5 ( 如图2 3 ) n o i g ) = 5 图2 3n o ( g 1 = 5 9 j h a h n 图 假设定理对于n o ( g ) n o ( e ) ，( g ) 4 的h a l i n 图日均成立，下面证明对 于g ，定理同样成立假设是所有满足引理2 2 中条件( i i ) 的w ( 只与一个内点相 邻) 的顶点集合，并让w 是w 中最小的一个顶点，令n ( w ) = u ，v l ，v 2 ，讥， 此处的u 是唯一的一个与w 相邻的内点， 1 ，钉2 ，仇是与t t ) 相邻的外点，设z 1 1 2 图的点可区别边染色 是与u 1 相邻的外点，x o ，x 1 是z 的另外两个邻点；y 是与u k 相邻的外点，y o ，y l 是 y 的两个邻点 情况1d ( w ) = 3 ： 令n ( w ) = “，v 1 ，u 2 ) 考虑 h = g 一 1 ，v 2 + 叫。，加可， 则由引理2 2 ，h 仍然是一个h a l i n 图且a ( h ) = ( g ) ，n o ( h ) = n o ( v ) 一1 根据 归纳假设，日有一个( n o ( v ) - 1 ) - v d e cf ，令色集合c = 【l ，2 ，n o ( c ) 一1 ) 情况1 1f ( w y ) c f ( z ) ，f ( w x ) c f ( 可) 不失一般性，假设 f ( w x ) = f ( y y o ) = 1 ，f ( w y ) = f ( x x o ) = 2 ， 则f ( y y l ) 聋c f ( ) ，y ( x x l ) 圣c f ( w ) 且y ( y y l ) f ( x x l ) 令f ( x x l ) = 4 ，厂( 可1 ) = 5 ，则无论边z 1 染什么颜色，c f ( x ) c f ( ) 总是成 立令g ( v l w ) = g ( v 2 y ) = n o ( g ) ，且g ( v l x ) = l ，g ( v l v 2 ) = 4 ，g ( 7 3 2 w ) = 2 情况1 2f ( w y ) q ) ，f ( w x ) q ( ) ( 对于情况f ( w y ) 隹c ， ) ，y ( w x ) q ( 可) ，证明方法类似，略) 假设 i ( w x ) = 1 ，f ( w y ) = f ( x x o ) = 2 ，i ( x z l ) = 4 因为f ( w x ) 聋c f 白) ，所以可令g ( v l w ) = 1 ，g ( v l v 2 ) = 3 ，g ( v 2 w ) = 2 ，再用新的颜 色n o ( g ) 去染边 u l z ，v 2 y 情况1 3i ( w v ) 隹c i ( z ) ，f ( w x ) 隹q ( ) 不失一般性，令，( 叫z ) = 1 ，i ( w y ) = 2 ，( u 叫) = 3 ，则1 萑q ( 可) 那么可令 g ( v l x ) = 1 ，g ( v l v 2 ) = 4 ，9 ( v 2 w ) = 2 ，并利用新的颜色n o ( g ) 去染边v 1 w ，v 2 y 1 2 2 图的点可区别边染色 情况2d ( w 1 = 4 ： 令n ( w ) = u ，v l ，1 ) 2 ，v 3 考虑图 日= g 一 u 1 ，v 2 ，v 3 + w x ，w y ， 则由引理2 2 可知，h 仍然是一个h a l i n 图，且n ( ) ( 日) = n o ( a ) 一2 若( h ) ( g ) ，那么日是一个3 - 正则h a l i n 图，根据定理2 1 ，x ：( h ) s 呦( 日) + 1 = n o ( g ) 一1 因此，h 有一个( m ( g ) 一1 ) 一v d e cf ，令其色集合 为c = l ，2 ，扎o ( g ) 一l 为完成对g 的染色，我们可以利用一个新的颜 色n o ( g ) 令 f ( w x ) = 1 ，f ( w y ) = 2 ，f ( u w ) = 3 显然，我们可以假设g ( v l z ) = g ( v 3 w ) = l ，9 ( v 3 b ) = 9 ( v 2 w ) = 2 ，g ( v l v 2 ) = 3 ，并令 g ( v 2 v 3 ) = g ( v l w ) = n o ( c ) 若a ( h ) = ( g ) ，由归纳假设可知，h 有一个( n o ( g ) 一2 ) 一v d e cf 令其 色集合为c = 1 ，2 ，n o ( a ) 一2 ，在完成g 的染色过程中，我们可以利用两个 新的颜色蛳( g ) 一l ，礼o ( g ) 由于d ( u ) 4 比d ( u ) = 4 时的证明更简单，所以不妨 设d ( u 1 = 4 令 f ( w x ) = 1 ，f ( w y ) = 2 ，厂( u 叫) = 3 显然，可令9 ( v l z ) = g ( v 3 w ) = 1 ，9 ( v 3 y ) = g ( v l w ) = 2 ，g ( v l v 2 ) = 3 ，并且令 g ( v 2 v 3 ) = 伽( g ) 一1 ，9 ( v 2 w ) = n o ( g ) 情况3d ( w ) 5 ： 令n ( w ) = u ，v l ，y 2 ，v a ( 。) 一1 考虑 h = g 一 u 1 ，1 ) 2 ，v d ( 。) 一1 + w x ，w y ， 若a ( h ) ( g ) ，染法类似于情况2 2 图的点可区别边染色 若a ( h ) = ( g ) ，那么由引理2 2 可知，h 仍然是一个h a l i n 图且n o ( h ) = n o ( g ) 一d ( w ) + 2 因为( 日) = a ( c ) 且d ( w ) 25 ，由叫的选取显然有n o ( c ) d ( 叫) + 4 根据归纳假设和引理2 3 ，h 有一个( n o ( c ) 一d ( w ) + 2 ) 一v d e c ，令 其色集合为c = t 1 ，2 ，n o ( g ) 一d ( w ) + 2 类似地，对于g 的染色，我们可以用另外的d ( w ) 一2 种颜色 n o ( c ) 一d ( w ) + 3 ，m ( g ) 一d ( w ) + 4 ，珈( g ) 去完成染色令 f ( w z ) = 1 ，l ( w y ) = 2 ，( u 叫) = 3 首先，令g ( v l z ) = l ，g ( v a ( 。卜l y ) = 2 其次，对任意的i t l ，2 ，d ( w ) 一2 ) ， 令g ( v i 仇+ 1 ) = i + 2 最后，令g ( v i w ) = n o ( g ) 一d ) + i + l ，i 2 ，3 ，d ) 一 1 ，g ( v l w ) = 4 其他e ( g ) 中未说明的边的染色与h 中对应的边相同，因此，g 有一个 佗o ( g ) 一v d e cg ，其色集合为 1 ，2 ，n 0 ( g ) ，所以定理成立 2 2 星、扇、轮联图的点可区别均匀边染色 设岛、r 、帆分别是几+ 1 阶的星、扇、轮图在下面的一些运算中，若其 结果大于2 孔+ 2 ，则取模2 亿+ 2 x 乙c & v & ，= 2 礼：2 ，：三： 证明设两个星图的点集和边集分别为v o ，口1 ， ， 晶，t ，i ，秽： ； 如仇ii = 1 ，2 ，礼，( v o v ：i1 = 1 ，2 ，礼) 则当礼2 时，v & 的度 1 4 2 图的点可区别边染色 序列为( n + 2 ，n + 2 ，n + 2 ，2 n + 1 ，2 n + 1 ) ，由度序列易计算 鹏v 啦k2 ，萎 情况1 他= 1 ：s 1vs 1 = k 4 ，由【4 】知结论为真 情况2t t = 2 ：岛v = bv 岛，由【6 】知结论为真 情况3t , 3 ：由( 1 1 ) 式，x 赢( v & ) 2 n 十2 所以我们仅需证明v & 存在( 2 n + 2 ) 一v d e e ce p - - i 设c = 1 ，2 ，2 n + 2 ，虿( 叫) = c c ( 叫) ，w y ( 岛v ) 情况3 1n 兰o ( m o d 2 ) 定义f 为：，( 珈) = 扎+ 2 ；，( 嵋口号) = 1 ；f ( v o v 詈) = 2 ；，( 珈秽等+ 1 ) = 扎+ 3 ； 厂( 瑶仇) ： + 詈+ 2 ， 1 ，詈一1 ) ； li + n + 2 ，i 考+ 1 ，几) ，( 嵋t ，：) = f ( v o v i ) = i + 1 ， i 1 ，詈 ； i 十詈十2 ，i 詈+ 1 ，佗， i + 挚+ 3 ，i l ，鸶一1 ) ； i + 1 ， i + 2 ，死 ，c 珈口：，= ；二；3 ，；兰；：l ：j _ ：， ，c 优巧，= ：；二；：；：歹兰雩：【：j ? n 对f ，有虿( 珈) = 1 ；虿( u 6 ) = 号+ 2 】- ； ，-_i，1li-，_j l l 一一 2 图的点可区别边染色 二= r _ 一一 时： 时 c ( u 暑) = 1 ，2 ) u + 2 ，咒+ 1 ) u 挚+ 3 ，2 n + 2 1 ； c ( u 争 1 ) = 1 ) u 考+ 3 ，孔+ 3 ) u 挚+ 3 ，2 n + 2 1 ； c ( v h = i + 2 ，i + 詈+ 2 ) u ( i + 扎+ 3 ，i + 挚+ 3 ) ，当i 1 ，詈一1 c ( u i ) = l + 1 ，i + 墨+ l iu i + n + 2 ，i + 警+ 2 ) ，当i 1 【营+ 2 ，礼， c ( u ：) = 1 ) 一，i + 2 ) u i + 3 ，2 n + 2 ，当t l 一，呈_ 时； c ( 口：) = i 一爹+ 2 ，i + 号+ 3 ) ，当i 考+ 1 ，礼 时 从而在染色f - f ，& v & 中任意两个顶点有不同的色集，故，是& v & 的 一个( 2 n + 2 ) 一v d e c 又 e i 墨+ 1 ， i 1 ，詈+ 2 ) u 扎+ 2 ，3 n 2 + 2 ； 詈+ 2 ， i ( 考+ 3 ，n + 1 ) u 警+ 3 ，2 n + 2 故，是& v & 的一个( 2 n + 2 ) 一v d e e c 倩况3 , 2 n 三l ( m o d 2 ) 当n = 5 时，定义，如下表2 1 所示： 此时易知，是一个1 2 正常边染色，且岛v 民中任意两个顶点有不同的色集， 故厂是& v 岛的一个1 2 一v d e c 又 ， 驯： 3 6 ，8 k l 4 ， 其它 、 故，是& v 的一个1 2 一v d e e c 1 6 2 图的点可区别边染色 表2 1 f v o 6 v lv 2v 31 3 4) 5 1 2l2345 v o 硝 1 2 23456 u i 674591 08 口5 7891 0l l1 2l 嵋 891 2l l5l7 呓 91 0l l 1 2l23 呓 1 0l l76234 当n = 7 时，定义，如下表2 - 2 所示： 耙2 f t j 0 嵋 v lv 2v 3u 4v 57 3 61 3 7 51 6l21 0678 v o 嵋 5 789l1 41 51 6 u ： 32l l1 21 31 41 51 6l t ，； 4 31 21 31 41 51 6l2 嵋 941 31 41 51 6l23 钉i l l1 03456281 5 呓 1 2l 14567891 0 u ： 1 31 2 5 6 7 391 0l l u ； 1 41 367891 0 l l1 2 此时易知f 是一个1 6 正常边染色，且s rv 函中任意两个顶点有不同的色集， 故，是岛v 岛的一个1 6 一v d e c 又 叫鞭 2 图的点可区别边染色 故厂是岛v 岛的一个1 6 一v d e e c 当礼9 时，定义厂为：，( 6 ) = 学；厂( u 6 u 学) = 1 ；厂( 如钞- - 。) = 礼+ 2 ；f ( v o u 字) = 1 ；f ( v o u 孚) = 2 ；，( 如u 字) = 扎+ 3 ；，( u l u ：) = 学； f ( v j v i ) = ，( 诺u ：) ，( 如) = f ( v o v i ) f ( v i v t n ) = i + 下n + l + 2 ， i + 几+ 2 ， i - 4 - 1 ， i + 半+ 2 ， i l ，孚】； i 字，扎) i 1 ，孚) ； i _ 【丁n + l ，孔 i + 2 ， i 1 ，字 ； i + 半+ 3 ，i l n + 2 l ，佗 i + 学+ 4 ，i l ，学 ； i + 1 ， i 学，n 】i i ，i 2 ，孚 ； i + 半+ l ，i 丁n + l ，n ，