（运筹学与控制论专业论文）关于图的邻点强可区别全染色的一些结果.pdf

摘要 摘要 本文所讨论的图均为有限无向的简单连通图 图的染色问题是图论研究的经典领域张忠辅等人在全染色的基础上，提 出了邻点可区别全染色和邻点强可区别全染色的概念设g ( ve ) 为阶不小于 2 的简单连通图，k 为正整数，厂是v ( g ) u e ( g ) 到 1 ，2 ，后) 的映射，满足：对 任意的u v e ( g ) ，f ( u ) ，( u ) ，f ( u ) 厂( 让u ) ，厂( u ) ，( u u ) ；对任意的z t v ，u w e ( g ) ( 秒叫) ，f ( u v ) 厂( u 叫) ；对任意的删e ( g ) ，c ( u ) c ( u ) ，其中c ( u ) = ，( 让) u ，( 删) i 仳秽e ( g ) ，v y ( g ) ) ，那么称厂为图g 的一个邻点可区别全 染色，简记为七一a v d t c ，且称x o t ( g ) = m i n k l g 有k a v d t c g 的邻点可区 别全色数若将上述c ( u ) 改为c ( 乱) = 厂( 札) ) l j f ( v ) l u v e ( g ) ，v y ( g ) ) u f ( u v ) l u u e ( g ) ，v y ( g ) ) ，其余条件不变，此时称f 为图g 的一个邻点强 可区别全染色，简记为尼一a v s d t c ，且称) ( 口，( g ) = m i n k l g 有k a v s d t c g 的邻点强可区别全色数 张忠辅等人讨论了一些特殊图如圈，完全图，完全二部图，树等的邻点可区 别全色数和邻点强可区别全色数，并提出猜想：( 1 ) 对于阶数不小于2 的简单图 g ，( g ) a ( g ) + 3 ；( 2 ) 若g 是最大度为的平面图，则x 口。( g ) ( g ) + 3 在本文中，我们主要研究一g 图的邻点可区别全染色和邻点强可区 别全染色在本文的第二章给出了一g 图的邻点可区别全色数，在第三章 中给出了一g 图的邻点强可区别全色数，第四章提出了可进一步探讨的 问题以供作者自勉 关键词圈；邻点可区别全染色；邻点强可区别全染色 a b s t r a c t a b s t r a c t a l lt h eg r a p h sc o n s i d e r e dh e r ea r ef i n i t e ，u n o r i e n t e d ，s i m p l ea n dc o n n e c t e d t h ep r o b l e mo nc o l o r i n go fg r a p h si sac l a s s i cs t u d yf i e l do fg r a p h t h e o r y b a s e d o nt h et o t a lc o l o r i n g ，z h a n gz h o n g f ue ta lp r o p o s e dt h ec o n c e p t so fa 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 ga n da d j a c e n t v e r t e x - s t r o n g - 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 l e tg ( ve ) b eac o n n e c t e dg r a p hw i t ho r d e ra tl e a s t2 ，ka p o s i t i v ei n t e g e ra n df am a p p i n gf r o m v ( v ) ue ( a ) t o 1 ，2 ，后) i f f o ra n yu v e ( g ) ，w eh a v e f ( u ) ，( u ) ，f ( u ) 厂( 仳 ) ，f ( v ) 厂( u u ) ；f o ra n yu v ，u w e ( g ) ( u ) ，w e h a v ef ( u v ) 厂( u 叫) ；a n df o ra n ye d g e u v e ( g ) ，w eh a v ec ( u ) 6 ( 7 3 ) ，w h e r e c ( u ) = - 厂( u ) ) u f ( u v ) l u v e ( g ) ，u y ( g ) ) ，t h e nf i sc a l l e da 尼一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 go fg ( k - a v d t c o fgi nb r i e 0a n dt h en u m b e r x a t ( g ) = m i n k l gh a sak - a v d t c i sc a l l e dt 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 g t o t a lc h r o m a t i cn u m b e ro fg i fc ( u ) = ，( u ) ) u f ( v ) l u v e ( g ) ，v y ( g ) ) u ，( 让口) f “口e ( g ) ，口y ( g ) ) ，a n dt h eo t h e rc o n d i t i o n sr e m a i n e d ，t h e n ，i sc a l l e d a 七一a d j a c e n t v e r t e x s t o n g d i s t i n g u i s h i n gt o t a lc o l o r i n go fg ( 七一a v s d t co fgi n b r i e f ) a n dt h en u m b e rx a s t ( c ) = m i n k l gh a sa 尼一a v s d t c i sc a l l e dt h ea d j a c e n t v e r t e x - s t r o n g 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 fg z h a n gz h o n g f ue ta ld i s c u s s e dt h ea d ja 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 ra n da d j a c e n t - v e r t e x - s t r o n g 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 s p e c i a lg r a p h s ，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 r e e se t c t h e yh a v eg i v e nt h e c o n j e c t u r e s ：( 1 ) f o ra n yc o n n e c t e ds i m p l eg r a p hgw i t ho r d e ra tl e a s t2 ，w eh a v e x o t ( a ) a ( c ) + 3 ( 2 ) i fg i sa p l a n eg r a p h ，w eh a v ex 口酣( g ) a ( c ) + 3 i nt h i s p a p e r , w es t u d ya 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 ga n d a d ja c e n t v e r t e x s t r o n g d i s t i n g u i s h i n gt o t a lc o l o r i n go f 一c i nc h a p t e r2 ，w e d e t e r m i n e dt 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 ro f 一g i nc h a p t e r3 ，w ed e t e r m i n e dt h ea d j a c e n t v e r t e x - s t r o n g 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 c n u m b e ro f 一g i nc h a p t e r4 ，w eb r i n gf o r w a r ds o m e q u e s t i o n st h a tn e e dt ob e r e s e a r c h e dd e e p e rf o rm y s e l f k e y w o r d s c i r c l e ；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 t v e r t e x s t r o n g 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 一l v _ i j l 刖舌 图论是一门发展迅速而又应用广泛的新兴学科，它最早起源于一些在民 间广泛流传的数学游戏的难题研究，如迷宫问题，博弈问题，棋盘上马的行走 路线问题等其中最早的文字记载出现在欧拉1 7 3 6 的论著中，这就是著名的 哥尼斯堡七桥问题，欧拉将这个问题转化为第一个图论问题，证明了这个问题 的结论是否定的，并推广了这个问题 像这些古老的数学游戏问题，当时吸引了很多学者的关注，学者们在研究 这些问题的基础上，又陆续提出了著名的网色猜想和哈密尔顿回路等问题 图的染色问题是图论研究的经典领域，它源于四色定理的研究，是图论研 究中一个很活跃的课题随着染色问题在现实中被j 。泛应用，各类染色问题被 相继提出并加以发展，应用图g 的一个( 正常) 七一染色是将七种染色分配给g 的顶点集v ( g ) ，使得相邻两顶点的颜色不同定义色数为：x ( g ) = m i n k l g 有 正常的七一染色1 类似的，图g 的一个( 正常) k 边染色是将七种染色分配给g 的边集e ( g ) ，使得有公共端点的两边的颜色不同边色数) ( ( g ) = m i n k l g 有 正常的七一边染色1 全染色的概念是对点染色和边染色的推广，是图论染色的 一个传统问题，由v i z i n g ( 1 9 6 4 ) 和b e h z a c l ( 1 9 6 5 ) 各自独立提出的图的全染色 是对图的点，边进行染色，使得相邻或相关联的两元素染色不同，图的全色数 x ( g ) = m i n k l g 有正常的七一伞染色】 在全染色的基础上，张忠辅等人提出了邻点可区别全染色和邻点强可 区别全染色的概念设g ( k e ) 为阶不小于2 的简单连通图，七为正整数，厂 是v ( g ) ue ( g ) 到( 1 ，2 ，尼) 的映射，满足：对任意的i t v e ( g ) ，f ( u ) ，( u ) ，f ( u ) y ( u v ) ，f ( v ) 厂( u u ) ；对任意的u v ，u w e ( g ) ( u 叫) ，f ( u v ) ，( u 叫) ；对任意的u v e ( g ) ，c ( u ) c ( u ) ，其中c ( “) = ，( u ) 】u f ( u v ) l u v e ( g ) ，v y ( g ) 】，那么称厂为图g 的一个邻点可区别全染色，简记为七一 a v d t c ，且称x d ( g ) = m i n k l g 有k a v d t c g 的邻点可区别全色数若将 上述c ( u ) 改为c ( u ) = _ ( ，( 钍) u f ( v ) l u v e ( g ) ，v y ( g ) ) u f ( u v ) l u v e ( g ) ，v y ( g ) ，其余条件不变，此时称。厂为图g 的一个邻点强可区别全染 色，简记为后一a v s d t c ，且称x 喊( g ) = m i n k l g 有七一a v s d t c 为g 的邻点强 可区别全色数 对于一个任意的图，确定其邻点可区别全色数和邻点强可区别全色数 h u百 是很困难的张忠辅等人讨论了一些特殊图，如圈，全图，完全二部图，树等 的邻点可区别色数和邻点强可区别全色数，并提出猜想：( 1 ) 对于阶数不小 于2 的简单图g ，x 。t ( g ) a ( a ) + 3 ；( 2 ) 若g 是最大度为的平面图，则 x a s t ( g ) a ( g ) + 3 在本文中，我们主要研究一g 图的邻点可区别全染色和邻点强可区 别全染色本文由以下章节构成： 第一章主要介绍了一些基本概念和已有结论： 第二章介绍了图一g 的邻点可区别全染色； 第三章讨论了图一g 的邻点强可区别全染色； 第四章中给出了一些可以进一步研究的问题 第1 尊绪论 第1 章绪论 1 1 基本概念 本文所讨论的图均为无向的有限简单图以下是文中经常用到的一些概 念和记号，未定义的概念和记号，均见参考文献【3 】 定义1 1 1 图g 是指一个有序三元组g = ( y ( g ) ，e ( g ) ，妒( g ) ) ，其中v ( g ) 是 非空的顶点集，e ( g ) 是不与v ( c ) 相交的边集，而矽( g ) 是关联函数，它使g 的每条边对应于g 的一个无序顶点对 若e 是一条边，而仳和u 是使得砂g ( e ) = u ? j 的顶点，则称e 连接钆和口；顶 点u 和v 称为e 的端点 定义1 1 2 如果一条途径有正的长且起点和终点相同，则称它是闭的若一条 闭迹的起点和内部顶点互不相同，则称它为圈长为k 的圈记为仇( 如图1 ) u 3 图1 若k 是奇数，则称瓯为奇圈；若k 是偶数，则称仇为偶圈 定义1 1 3 若和g 是两个互不相交的圈，在中的一点和g 中的一点 之间连一条边所得到的图称为一g 图( 如图2 ) 定义1 1 4 将图g 的一条边e 删去并使它的两个端点重合，这样得到的图记 为g e ，此时也称g 的边e 被收缩 第1 章绪论 图2 定义1 1 5 设图g = ( ke ) 是一个阶至少为2 的连通简单图，k 是一个正整数， ，是v ( c ) ue ( g ) 到 1 ，2 ，忌) 的映射，对任意的u y ( g ) ，其色集合记为 c ( u ) = 【，( 也) ) u 【厂( u 口) iu v e ( g ) ， y ( g ) ) ，如果 ( 1 ) 对任意的u v ，u w e ( g ) ，u w ，有f ( u v ) 厂( 伽，) ； ( 2 ) 对任意的u v e ( g ) ，有f ( u ) 厂( u ) ，f ( u ) f ( u v ) ，y ( v ) ，( u 口) ； 则称厂是g 的七一正常全染色进一步，如果。厂还满足 ( 3 ) 对任意的 1 2 v e ( g ) ，有c ( u ) c ( 口) ， 则称，是g 的七一邻点可区别全染色( 简记为尼一a v d t c ) 称 m i n k l g 有七一a v d t c 为g 的邻点可区别全色数，记作x 口t ( g ) 猜想1 【1 5 】对于阶数不小于2 的简单图g ，x 口( g ) a ( a ) + 3 定义1 1 6 设图g = ( ve ) 是一个阶至少为3 的连通简单图，k 是一个正整数， 厂是v ( a ) ue ( g ) 到 1 ，2 ，庇】的映射，对任意的u y ( g ) ，其色集合记为 c ( u ) = 厂( u ) u 厂( 口) iu v e ( g ) ，u v ( c ) u f ( u v ) l 乱u e ( g ) ，秽y ( g ) ) ， 如果 ( 1 ) 对任意的u u ，v w e ( g ) ，u w ，有y ( u v ) ，( u 叫) ； ( 2 ) 对任意的u v e ( g ) ，有y ( u ) t 厂( u ) ，y ( u ) f ( u v ) ，y ( v ) ，( u u ) ； ( 3 ) 对任意的u v e ( g ) ，有c ( u ) c ( ) ； 则称_ 厂是g 的七一邻点强可区别全染色( 简记为k - a v s d t c ) 称 m i n k l a 有k a v s d t c 为g 的邻点强可区别全色数，记作x o 。t ( g ) 猜想2 【1 6 】若g 是最大度为的平面图，则x o 。t ( g ) ( g ) + 3 定义1 1 7 一条边的端点称为与这条边关联，与同一条边关联的两个顶点称为 是相邻的点，与同一个顶点关联的两条边称为相邻的边 一4 一 第1 章绪论 定义1 1 8 若图g 中的每一对顶点恰有一条边连接，则称图g 为完全图阶数 为礼的完全图记为 定义1 1 9 如果图g 的顶点集可以分解为两个非空子集x 和y ，使得每条边 都有一个端点在x 中，另一个端点在y 中，则称图g 为偶图( 或二部图) ，这样 的一种分类( x ，y ) 称为图g 的一个二分类 具有二分类( x ，y ) 的简单偶图，若x 的每个顶点都与y 的每个顶点相连， 则称这样的图为完全偶图( 或完全二部图) ，若l x i = m ，i y l = n ，这样的图记为 k m ，n 定义1 1 1 0 图g 中点u 的度d v ( v ) 即图g 中与点v 相关联的边数；图g 的最 大度a ( a ) 和最小度6 ( g ) 分别为图g 中点度的最大值和最小值 定义1 1 1 1 如果图g = ( v e ) 中任意两个顶点u ，v 之问都存在一条路，则称 图g 是连通图，否则称为非连通图 定义1 1 1 2 u ，u 两点问连三条内部不相交的路且至多有一条长度为1 的图， 称为p 一图u ，u 两点间连k ( k 4 ) 条内部不相交的路且至多有一条长度为1 的图，称为广义0 一图，并简记为巩 1 2 相关结论 为了证明本文的主要结果，我们给出如下引理。其证明可以在给出的文献 中找到 引理1 2 1 【1 5 】设图g 是阶不小于3 的图，x d ( g ) a ( a ) + 1 ；若g 中有两个 最大度点相邻，则有x n ( g ) a ( a ) + 2 引理1 2 2 【1 5 】若图g 具有k 个连通分支g 1 ，g 2 ，g 知，且i v ( a i ) l 2 ( i = l ，2 ，尼) ，贝0 ) ( n ( g ) = m a x x 口t ( g 1 ) ，) ( n t ( g 2 ) ，x 口( g 七) 】 引理1 2 3 1 5 1 设g 表示n 阶圈，则x n ( g ) = t t = 3 ： n 4 引理1 2 4 “1 5 】设表示n 阶完全图，t t 3 ，则 c ，= 协：n _ = 0 ( 。删m o d 2 2 一) ； 第l 章绪论 引理1 2 5 【1 5 】对于完全二部图，n ( m 7 , 1 ) ，有 x 武( ，n ) = 3 ，m m = 佗= 1 ； im + 1 ， 礼+ 1 ； 【礼+ 2 ，m = n 2 i j l 理1 2 6 1 6 】设图g 是阶不小于3 的图，则x a s t ( g ) a ( g ) + 1 ；若g 中至少 有两个最人度点相邻，则有x n 。( g ) a ( g ) + 2 引理1 2 7 【1 6 设g 表示n 阶圈，则当n 4 ，1 0 ，且n 为偶数时，x o 。t ( g ) = 4 ； 其他情形均为x o 。( g ) = 5 引理1 2 8 【1 6 】设表示几阶完全图，n 3 ，则x 捌( ) 佗+ l 0 9 2 礼1 ，其中 f l 0 9 2 n 表示不小于l 0 9 2 1 7 , 的最小整数 本文我们主要得到了如下结论： 定理2 1 1 对于m 3 ，n 3 ，有x o t ( c m g ) = 5 推论2 2 1 对于仇4 ，n 4 ，e 为图一g 的任意一条边，则 x 越( ( 一g ) e ) = 5 引理3 1 1 对于图g 的任意一个邻点强可区别全染色，若伽e ( g ) ，且u 在 厂下的色集合l c ( u ) i = 3 ，则c ( u ) 妄c ( u ) ，i c ( u ) i 4 引理3 1 2 对于奇圈g 的任何一个5 - a v s d t c ，必存在点v y ( g ) ，使得 在厂下的色集合i c ( v ) i = 4 引理3 1 3 对于圈g ，若尬( g ) = 5 ，则存在圈g 的一个5 a v s d t c ，使得 在此厂下，至少有一点的色集合所含元素个数为5 定理3 2 1 对于m 3 ，t , 3 ，有x o 。( 一g ) = 5 推论3 2 1 对于m 4 ，n 4 ，e 为图c m g 的任意一条边，则 x 础( ( 一g ) e ) = 5 一6 一 第2 章一g 图的邻点可i ) ( 别全染色 第2 章c r 仇一g 图的邻点可区别全染色 本章我们主要通过给出一g 图的一种正常全染色的方法，并证明该 染色是邻点可区别的，进而确定一g 图的邻点可区别全色数 2 1 主要结论 首先，我们给出本章的主要结论 定理2 1 1 对于m 3 ，n 3 ，有x 口( 一g ) = 5 证明显然，图一g 的最大度为3 ，且有两个最大度点相邻，由引理1 2 1 可 知，) ( 。( 一g ) 5 为了证明x a t ( 一g ) = 5 ，只需给出一g 的一 种5 邻点可区别的全染色方法即可 为了叙述方便，设 c m = “1 u 2 u m u l ，( = v l v 2 u n u l ， 且乱l u l e i u m 一八则图纠，开化u r n + 1 有i 9 - u l ，化+ 1 有丫 ：v l 分三种情形证明： 情形1 当m 三0 ( m o d2 ) ，佗兰0 ( m o d2 ) 时， 定义染色函数f ：y ( 一g ) ue ( 一g ) 一 1 ，2 ，5 ) 如下： f ( u i ) = 铿霪= 。1 ( ( m m o d 2 0 d2 ) ) ，1 1 2 ， m ，( u t ) = ；：= 三。1 ( ( m m 。o d d2 2 ) ) ；z = l ，2 ，n ，u i u i + 1 ) = 侄吲- - - 1 ( m m o d 2 0 d2 ) ) ，l ，2 ，m ，v i v i + 1 ) = r 引= - 1 ( 删m o d2 2 ) ) ，1 1 2 ，n 一1 一 第2 章 e m c 。图的邻点可区别全染色 f ( u l v l l = 5 显然所定义的染色函数t 厂是一个5 - 正常全染色因为c ( 钆1 ) = 1 ，3 ，4 ，5 ) ，c ( v 1 ) = 【2 ，3 ，4 ，5 ) ，所以c ( u 1 ) c ( v 1 ) ，而且对2 i m ，2 j 佗，有 c ? - 1 i ，= 瓣引- 1 ( m m 砌o d2，)； c ( 小滁；三- = 0 ( m 1 ( m 枷o d2 ) ) ； 因此，的确是m 三0 ( m o d2 ) ，n 三0 ( r o o d2 ) 时图一g 的一个5 - a v d t c 情形2 当m 三1 ( r o o d2 ) ，n 三0 ( m o d2 ) 时， 定义染色函数厂：y ( c f m g ) ue ( 一g ) _ 1 1 ，2 ，5 ) 如下： m 扣娃引- - 1 ( 删m o d2 2 ) ) ；i - - 1 , 2 , , m - 1 ，( u m ) = 5 2 _ 1 d ：2 ；江1 2 ，亿 1 ，i 三0 ( m o d2 ) ； 一 3 - 1 5 r o o d2 。) 、；江1 1 2 ，m 乩 4 ，i 三0 ( r o o d2 ) ； 一 厂( u m u l ) = 2 ，c u t u i + - ，= 主：i ；- - 三。1 。( m m o 。d d2 2 ，) ；t = ，2 ，n 1 ( u , v 1 1 = 5 显然所定义的染色函数厂是一个5 - 正常全染色因为c ( u 1 ) = 1 ，2 ，3 ，5 ) ，c ( v 1 ) = 2 ，3 ，4 ，5 ) ，所以c ( u 1 ) c ( 1 ) 又c ( u m ) = 【2 ，4 ，5 ) ，而 且对2 i m 一1 ，2 j n ，有 一8 一 ，j【，一l = | l 仇 h 他 帅 u ， 釜：兰盘二垒型塑坠坠型篁些二! 竺竺! ! 一 c ( u i 、= c ( 吻) = 1 ，3 ，4 ) ，i 三1 ( m o d2 ) ； 2 ，3 ，4 ) ，i 三0 ( r o o d2 ) ； 1 ，3 ，4 ) ，j 三1 ( r o o d2 ) ； 2 ，3 ，4 ) ，j 三0 ( m o d2 ) ； 因此f 的确是m 兰1 ( m o d2 ) ，n 三0 ( m o d2 ) 时图一g 的一个5 - a v d t c 情形3 当m 三1 ( r o o d2 ) ，n 三1 ( m o d2 ) 时， 定义染色函数f ：y ( 一g ) ue ( 一g ) 一 1 ，2 ，5 ) 如下： 厂( 仳t ) ，( 仇) 1 注1 ( m o d ：2 ；i 乩2 ，m 乩 2 ，i 三0 ( r o o d2 ) ； f ( u m ) = 5 2 一1 ( m o d1 2 ；z _ 1 ，2 ，礼_ 1 1 ，i 三0 ( r o o d2 ) ； 厂( ) = 5 f ( u i u i + 1 ) = r 引= 1 ( 删m o d2 2 ) ) ，1 ，2 ，一， ，( u m u l ) = 2 ，v i v i + 1 ) = - b 注i = - 。l 。( m m o d2 ) ；忍 f ( u 他v 1 ) = 1 ，f ( u l v l ) = 5 显然所定义的染色函数，是一个5 一正常全染色因为c ( u 1 ) = 1 ，2 ，3 ，5 ) ，c ( v 1 ) = 1 ，2 ，4 ，5 ) ，c ( u 仇) = 2 ，4 ，5 ) ，c ( v n ) = 1 ，3 ，5 ) ，而且对 2 i m 一1 ，2 j 他一1 ，有 9 ，f、_，1一， ，l，【 第2 孥c m c 。图的邻点可区别全染色 c c u t ，= ：i ：三；：；i 三- 。1 。( m m 。o d d 2 2 ，) ； c c ，= ；：i ：三；：j 歹三- - 。1 。( m m o 。d d2 2 ，) ； 因此，的确是m 三1 ( m o d2 ) ，n 三1 ( m o d2 ) 时图 综上所述，定理得证 2 2 一个推论 本节，我们将给出一个推论 一g 的一个5 一 推论2 2 1 对于m 4 ，n 4 ，e 为图一g 的任意一条边，则( ( 一g ) e 1 = 5 证明设= u 1 u 2 乱m u l ，g = u i v 2 v n v l ，且“1 u 1 e ( 一g ) ，并把 u m + 1 看作乱1 ，把+ 1 看作v 1 分两种情形证明： 情形1 若e e ( ) ue ( g ) ，则将e 收缩后所得到的图为一1 一g 或 一g 一1 ，由定理2 1 1 知结论成立 情形2 若e 聋e ( ) ue ( g ) ，即e = u l 口1 此时将e 收缩后所得到的图如 图3 ， 图3 显然其最大度为4 ，由引理1 2 1 可知，x 口t ( ( e r a g ) e ) 5 为了 证明) ( 耐( ( 一g ) e ) = 5 ，只需给出( 一g ) e 的一种5 - 邻点可区别 第2 章c m c 。图的邻点可i 刖令染色 的全染色方法即可我们先分别对和g 分别进行着色由引理1 2 3 知， x 。( ) = x a t ( g ) = 4 ，于是可设 ，止分别是和g 的4 - a v d t c ，而且经 过适当的颜色调换可以使得 ( u 1 ) = 1 ，f l ( u l u 2 ) = 4 ， ( u 1 乱m ) = 2 ， 尼( v 1 ) = 1 ，如( u l u 2 ) = 3 ，尼( y l y n ) = 5 ， 再将此时的 ，尼合并成，即： f ( u i ) = f x ( u d ，f ( v i ) = f z ( 眈) ， y ( u i u i + 1 ) = ( t i u i + i ) ，y ( v i v i + 1 ) = f 2 ( v i v i + 1 ) 易见此时的厂就是( 一g ) e 的一个5 - a v d t c ，从而结论成立 筇3 巷 c m c 。图的邻点强可【x 别全染色 第3 章一g 图的邻点强可区别全染色 本章我们先在第一节给出几个关于图的邻点强可区别的引理，至于图 c m g 的邻点强可区别全色数将在第二节中给出 3 1 几个引理 首先，我们给出关于一般图的邻点强可区别全染色的一个结论 引理3 1 1 对于图g 的任意一个邻点强可区别全染色厂，若u u e ( g ) ，且u 在 ，下的色集合i c ( u ) i = 3 ，则c ( u ) 三c ( ) ，i c ( v ) l 4 证明因为u o e ( g ) ，i c ( 让) l = 3 ，而厂( 乱) ，厂( u ) ，i ( u v ) 互不相同，且 厂( u ) ，厂( 钉) ，- 厂( 乱u ) ) c ( “) ，于是c ( u ) = 【，( u ) ，( ) ，厂( u u ) ) 又因为c ( u ) c ( u ) ， ，( u ) ，厂( u ) ，( u u ) ) c ( u ) ， 所以c ( u ) 主c ( u ) ，i c ( u ) f 4 一 下面我们再给出关于圈的邻点强可区别全染色的两个引理 引理3 1 2 对于奇圈g 的任何一个5 - a v s d t c ，必存在点v y ( g ) ，使得口 在，下的色集合i c ( u ) i = 4 证明( 反证法) 设，是奇圈g 的一个5 a v s d t c ，对任意的v y ( g ) ，有 3 i c ( u ) i 5 ，若结论不成立，则对任意的v y ( ) ，有i c ( u ) j = 3 或 l c ( u ) i = 5 分两种情形证明： ( 1 ) 若i c ( u ) i = 3 ，由引理3 1 1 知，v 的邻点u 的色集合l c ( 乱) l = 5 ； ( 2 ) 若l c ( u ) l = 5 ，因为，是5 - a v s d t c ，所以v 的邻点u 的色集合l c ( u ) j 5 ，故l c m ) i = 3 ； 于是g 的各个顶点的色集合所含的元素个数必定是3 和5 相间地排列， 从而g 只能是偶圈，矛盾 引理3 1 3 对于圈g ，若) ( 。t ( g ) = 5 ，则存在圈g 的一个5 一a v s d t c 厂，使得 在此厂f ，至少有一点的色集合所含元素个数为5 筇3 蕈c m c 。图的邻点强n 区别令染也 证明因为x 口( g ) = 5 ，由引理1 2 7 知，n = 4 或仡= 1 0 或n 为奇数为了方 便，可设g = v l v 2 u l ，且把v n + 1 看作v l ，我们只需对下面各种情形分别 构造圈g 的满足条件的5 - a v s d t c 情形1 当n = 3 时，构造厂如下： 对i = 1 ，2 ，3 ，令f ( v i ) = i ，f ( v l t 3 2 ) = 5 ，f ( v 2 v 3 ) = 1 ，f ( v a v 4 ) = 4 ； 容易验证这个，是g 的一个满足条件的5 - a v s d t c 情形2 当佗= 4 时，构造，如下： f ( v 1 ) = f ( v 3 ) = 2 ，f ( v 2 ) = 1 ，f ( v 4 ) = 3 ，f ( v l t l 3 2 ) = f ( v 3 v 4 ) = 4 ，f ( v 2 v 3 ) = f ( v 4 饥) = 5 ； 容易验证这个，是a 的一个满足条件的5 - a v s d t c 情形3 当佗= 1 0 时，构造厂如下： ，c耽，=奏；j三主；薹；，c忱+，=薹 i = 1 ，6 ； i = 2 ，7 ； i = 3 ，8 ；f ( v l v l o ) = 4 i = 4 ，9 ； i = 5 ： 容易验证这个厂是a o 的一个满足条件的5 - a v s d t c 情形4 当仡为奇数，且n 5 时 情形4 1 当n 三0 ( m o d5 ) 时，构造，如下： f1 ，i 三1 ( m o d5 ) ； l 2 ，i 兰2 ( r o o d5 ) ； f ( v i ) = 3 ，i 兰3 ( m o d5 ) ；i = 1 ，2 ，死 i4 ，i 三4 ( m o d5 ) ； 【5 ，z 三0 ( m o d5 ) ； ，c忱仇+，=蓁； 一1 3 一 l n21 1 1 、，、1，、l，、，、， 5 5 5 5 5 d d d d d o o o o o m m m m m ，l，j，j、 1 2 3 4 0 三 兰 三 兰 三 ：0dz 筇3 孳 c m g 图的邻点强可区别全染色 ，( u n 钞1 ) = 4 此时c 0 1 ) = ( 1 ，2 ，3 ，4 ，5 ) ，c ( v n ) = 【1 ，4 ，5 ) ，对2 i n 一1 ， i 三1 ( r o o d5 ) ； i 三2 ( r o o d5 ) ； i 兰3 ( r o o d5 ) ； i 三4 ( r o o d5 ) ； i 三0 ( r o o d5 ) 因此这个厂是礼三0 ( r o o d 5 ) 时g 的一个满足条件的5 - a v s d t c 情t 髟4 2 当礼三1 ( r o o d5 ) 时，构造，如下： 对i = 1 ，2 ，3 ，4 ，令，( 饥) = z ，( u 5 ) = 2 ，1 厂( ) = 5 ，f ( v l v 2 ) = 3 ，f ( 2 ) 2 v 3 ) = 1 ，( u 3 u 4 ) = 5 ，y ( v 4 口5 ) = 3 ，( 口5 u 6 ) = 1 ，y ( v 6 v t ) = 4 ；当7 i n 时，令 i 1 ， i 2 ， ，( 仇) ： 3 ， h t 三2 ( r o o d5 ) ； i 三3 ( r o o d5 ) ； i 三4 ( r o o d5 ) ； i 三0 ( r o o d5 ) ； i 兰l ( r o o d5 ) ；玳阱扣锤 i 三2 ( r o o d5 ) ； i 三3 ( r o o d5 ) ； i 三4 ( r o o d5 ) ； i 三0 ( r o o d5 ) ； i 三1 ( m o d5 ) 对如此构造的，我们有c ( v 1 ) = 1 ，2 ，3 ，5 ，c ( v 2 ) = 1 ，2 ，3 ) ，c ( v 3 ) = ( 1 ，2 ，3 ，4 ，5 ) ，c ( v 4 ) = 2 ，3 ，4 ，5 ) ，c ( v s ) = 1 ，2 ，3 ，4 ，5 ) ，c ( u 6 ) = 1 ，2 ，4 ，5 ) 以及 c ( v r ) = 1 ，2 ，3 ，4 ，5 ) ；且当8 i i 三1 ( r o o d5 ) ； i 三2 ( r o o d5 ) ； i 三3 ( r o o d5 ) ； i 三4 ( m o d5 ) ； i 兰0 ( r o o d5 ) 因此这个。厂是礼三1 ( r o o d 5 ) 时g 的一个满足条件的5 - a v s d t c 情形4 3 当佗兰2 ( r o o d5 ) 时，构造厂如下： 对i = 1 ，2 ，3 ，4 ，5 ，令，( 仇) = i ，( 4 ) = 4 ，y ( v 7 ) = 2 ，y ( v l v 2 ) = 3 ，f ( u 2 v 3 ) = 4 ，y ( v 3 v 4 ) = 2 ，y ( v 4 v 5 ) = 1 ，y ( v s v 6 ) = 3 ，y ( v 6 v 7 ) = 1 ，y ( v t v s ) = 5 ；当8 i 礼 时。令 一1 4 一 、，、，、t、， 5 4 5 5 5 3 3 4 4 4 ， ， ， ， ， 2 2 3 3 2 ， ， ， ， ， 1 1 o 二1 1 r t r l r l r t r t ，l，、-_一 = 、i ， ，l c 5 ， ， ， ，、j 1 j 1 j销讣，q 讣 ，、j ， j 曩& 射及出磊幺磊幺& l l l l 幺 = 仇c 第3 章一c 。图的邻点强可别个染色 i 1 ， l 2 ， ，( 仇) ： 3 ， i 兰3 ( m o d5 ) ； i 三4 ( m o d5 ) ； i 三0 ( m o d5 ) ； i 三l ( m o d5 ) ； i 三2 ( m o d5 ) ； f f ( v i v i + 1 ) = 【 对如此构造的厂，我们有c ( v 1 ) = 1 ，2 ，3 ，5 ) ，c ( v 2 ) = 【1 ，2 ，3 ，4 ) ，c ( v 3 ) = 2 ，3 ，4 ) ，c ( u 4 ) = 1 ，2 ，3 ，4 ，5 ) ，c ( u 5 ) = 1 ，3 ，4 ，5 ) ，c ( u 6 ) = 1 ，2 ，3 ，4 ，5 ) 以及 c ( v 7 ) = l ，2 ，4 ，5 1 ；且当8 i 佗， 沪罐嚣 i 三1 ( m o d5 ) ； i 三2 ( m o d5 ) ； i 三3 ( m o d5 ) ； i 三4 ( m o d5 ) ； i 三0 ( m o d5 ) 因此这个厂是n 三2 ( m o d 5 ) 时g 的一个满足条1 ：，| ：的5 一a v s d t c 情f 眵4 4 当n 三3 ( m o d5 ) 时，构造f 如下： 对i = 1 ，2 ，3 ，令( v i ) = i ，f ( v l v 2 ) = 5 ，f ( v 2 v 3 ) = 1 ，f ( v 3 v , ) = 4 ；当4 i 礼时，令 卜 ，( 忱) = 3 ， i 三4 ( m o d5 ) ； f 5 ，i 三4 ( m o d5 ) ； i 三0 ( m o d5 ) ；l1 ，i 三0 ( m o d5 ) ； i 三1 ( m o d5 ) ；，( 忱仇+ 1 ) = 2 ，i 三1 ；( m o d5 ) ； i 三2 ( m o d d5 ) ；l3 ，i 兰2 ( m o d5 ) ； i 三3 ( m o d5 ) ；【4 ，i 三3 ( m o d5 ) 对如此构造的厂，我们有c ( v 1 ) = 1 ，2 ，4 ，5 ) ，c ( v 2 ) = 1 ，2 ，3 ，5 ) ，c ( v a ) = 1 ，2 ，3 ，4 1 ，c ( v 4 ) = 1 ，2 ，3