（应用数学专业论文）图的邻点可区别正常边染色的一些结果.pdf

摘要 一个图g 的正常边染色称为是邻点可区别的，如果对g 的任意两个楣邻的顶点乱和 来说，与u 关联的所有边的颜色构成的集合异于与v 关联的所有边的颜色构成的集合显 然一个图g 有邻点可区别正常边染色当且仅当g 不含孤立边对一个无孤立边的图g 进 行邻点可区别的正常边染色所需要的最少的颜色数称为是g 的邻点可区别正常边色数， 记为疋( g ) 本文对xp n ，晶。g ，磺，单圈图及几类完全乒部图的邻点可区别正常边 染色进行了讨论，确定了它们的邻点可区别正常边色数这些结果说明邻点可区别正常 边染色猜想( 对任意连通简单图g ，如果iy ( g ) i 6 ，则( g ) 童瑶( g ) ( g ) + 2 ) 对这 些图是成立的对最小度至少是5 ，最大度小于! 呜业的n 阶图g ，给出了其邻点可区别的 正常边色效的一个上界f m l ，其中实数c 满足o c ； 关键词：正常边染色：邻点可区别正常边染色：邻点可区别正常边色数 a b s t r a c t a p r o p e r e d g e c o l o r i n g o f g i s c a l l e d 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 g i f a n y t w oa d j a c e n t v e r t i c e st a n dt ，a r ei n c i d e n tt od i f f e r e n ts e t so fc o l o r e de d g e s o b v i o u s l y , ag r a p hg h a sa d j a c e n tv e r t e xd i s t i n g u i s h i n gp r o p e re d g ec o l o r i n gi fa n do n l yi fgh a sd oi s o l a t e d e d g e s t h em i n i i n u i nn u m b e rr e q u i r e df o ra na d j a c e n tv e r t e xd i s t i n g u i s h i n gp r o p e re d 薛 c o l o r i n go fg i sc a l l e dt 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 gp r o p e re d g ec h r o m a t i cn u m b e r ， d e n o t e db y 也( g ) t h ea d j a c e n tv e r t e x 血蚵n 目l 础j d gp r o p e re d g ec h r o m a t i cn u m b e r s o fp mxr ，p m g ，磺，m o n o c y c l eg r a p ha n ds e v e r a lc o m p l e t e4 - p a r t i t eg r a p h sa r e d i s c u s s e da n dt h ea d j a c e n tv e r t e xd i s t m g i l j s h j n gp r o p e re d 驴c h r o m a t i cn u m b e r so ft h e m a r eo b t a i n e di nt h i sp a p e r t h e s er e s u l t si l l u s t r a t et h a tt h ea d j a c e n tv e r t e xd i s t 啦h i | 1 9 p r o p e re d g ec o l o r i n gc o n j e c t u r e ( f o ra n yc o n n e c t e dg r a p hg ，j y ( g ) j 6 ，w eh a v e ( 回 兄( g ) ( g ) + 2 ) i st r u ef o rt h e s eg r a p h s a n da nu p p e rb o u n do ft 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 gp r o p e re d g ec h r o m a t i cn u m b e ri sg i v e nf o rac l a s sg r a p hw i t h 占5a n d ! 掣，w h e r e0 n ，约定t = t 叼= v 4 - j = 桃。，i = 1 ，2 ，m ，j = 1 ，2 ，n ，其中兰 r ( m o d m ) ，j 三s ( m o d n ) 分两种情形考虑： 情形1m 2 ，n 5 由引理1 1 仅需证p 2 g 有4 一a v d p e c , p m g 有 5 一a v d p e c ( m 3 ，f t 3 ) 如下构造p m g 的一个邻点可区别正常边染色，： 情形1 1neo ( m o d 3 1 对每个j ( 1 jsn ) ，w i i w ( i + 1 ) j ( i = 1 ，2 ，m 1 ) ，依次用颜色4 ，5 循环去染；边 w i i w i ( i + 1 ) u = 1 ，2 ，n - 1 ) ， 为奇数时，依次用颜色1 ，2 ，3 循环去染；t 为偶数时，依次用 颜色3 ，1 ，2 循环去染此外对l , i = 2 4 ，6 j 时，有口) o = 1 ，2 ，n 一1 ) 循环地等于 1 ，2 ，3 ； = 3 ，5 ，7 ，时，有0 ( 蛳) u = 1 ，2 ，n 1 ) 循环地等于2 ，3 ，1 易见当m = 2 时， 0 u ) 0 = 1 ，2 ，而依次循环地等于 2 ，5 ， 3 ，毋， 1 ，5 ，0 ( t ) 0 = l ，2 ，n ) 依次循环地等于 1 ，5 ) ， 2 ，5 ) ， 3 ，5 ) 因此，是邻点可区别正常边染色 情形1 2n 兰l ( m o d 3 ) 边w i j w ( i + 1 h d = 1 ，2 ， 为奇数时，前4 条边依次用颜色3 ，4 ，l ，2 染，以 后用颜色3 去染；i 为偶数时，用颜色5 去染；边蛳t n i u + 1 ) o = 1 ，2 ，n ) ， 为奇 数时，前4 条边依次用颜色1 ，2 ，3 ，4 染，以后用色l ，2 ，4 循环去染；为偶数时，前4 条边依次用颜色2 ，3 ，4 ，1 染，以后用颜色2 ，4 ，1 循环去染此外对，i = 2 ，4 ，6 ， 时，前4 个顶点的口( ) u = 1 ，2 ，n 一1 ) 依次等于4 ，1 ，2 ，3 ，以后循环地等于 4 2 r 和r 。( 夏的邻点可区别正常边染色 4 ，1 ，2 ；i = 3 ，5 ，7 ，时，前4 个顶点的0 ( t ) 0 = 1 ，2 ，n 一1 ) 依次等于2 ，3 ，4 ，1 ， 以后循环地等于2 ，4 ，1 ；易见当m = 2 时，前4 个顶点的g ( 雌j ) u = 1 ，2 ，n ) 依 次等于 2 ，5 ) ， 3 ，5 ， 4 ，5 ) ， 1 ，5 ，以后循环地等于 2 ，5 ) ， 4 ，5 ) ， 1 ，5 ) ，前4 个顶点的 0 ( 奶j ) c j = 1 ，2 ，哟依次等于 1 ，5 ) ， 2 ，5 ) ， 3 ，5 ) 以后循环地等于 4 ，5 ) ， 1 ，5 ， 2 ，5 ) 且c ( t h l j ) o ( w l o + 1 ) ) 。g ( 让协) g ( 。叶1 ) ) o = 1 ，2 ，n 一1 ) 因此，是邻点可区 别正常边染色一 情形1 3n 三2 ( r o o d 3 ) 边t ( m h o = 1 ，2 ， ) ，i 为奇数时，前8 条边依次用颜色3 ，4 ，1 2 循环去染， 以后用颜色3 去染；i 为偶数时，用颜色5 去染；边咄，啦叶1 ) o = l ，2 ，n ) ，i 为奇数时， 前8 条边依次用颜色l ，2 ，3 ，4 循环去染，以后用颜色1 ，2 ，4 循环去染；i 为偶数时，前8 条 边依次用颜色2 ，3 ，4 ，1 循环去染，以后用颜色2 ，4 ，1 循环去染类似于情形1 2 ，易知该染 色是邻点可区别正常边染色因此，当m ；2 时，是4 一a v d p e c ；当m 3 时， 是5 一a v d p e c 情形2 当m = 2 ，n = 5 时，由引理1 1 知，吐( 马c 5 ) 4 先证p 2 g 不存在 4 - a v d p e c 假设马c 5 存在4 一a v d p e c ，定义映射f ：e ( p 2 c 5 ) 一 l ，2 ，3 ，4 ) ， 令最= e e ( 马c 5 ) l f ( e ) = 0 断言1 每种颜色i ( 1 ，2 ，3 ，4 ) 至多染了4 条边 证明反设某个l 风l i = 5 ，有下列三种情形： 情形1 1f ( w l t 忱i ) = o ，i = 1 ，2 ，3 ，4 ，5 则除 o 外的其余3 种颜色染的是b g 中 两个圈侥的边，必出现某圈上的一边的两邻边染同色，与邻点可区别正常边染色矛盾! 情形1 2i 劬t j 2 i ，l u ) = o l i 1 ，2 ，3 ，4 ，5 i = 3 由于是邻点可区别的正常 边染色，这些i 必连续，不妨设i = l ，2 ，3 ，即，( 叫1 1 t j 2 1 ) = ，1 2 t 忱) = ，扣1 3 t 峪) = i o ， 则必有l ( w m 0 1 5 ) = ，( t t ) = o 不妨设其余三种颜色为1 ，2 ，3 ，若，1 1 2 ) = 1 ， 则，( 撕2 铆3 ) = 2 或3 ( 不妨取2 ) ，必有，1 3 1 ) 1 4 ) = 3 ，如1 l t l j l 5 ) = 3 ，( 铆4 耽4 ) = 1 ，f ( w 1 5 ) = 2 ，( 她l 劬2 ) = 2 或3 ( 不妨取2 ) ，则，2 l 地5 ) = 1 ，( t c j 2 2 砌) = 3 ，( t 吻叻4 ) = 1 但，( ”1 4 t 嗡) = 1 ，矛盾! 若，( 耽l 毗2 ) 一3 ，则只能是，( 耽l 忱5 ) = 2 ，但 f ( w 1 5 也5 ) = 2 ，矛盾! 若，1 2 1 1 2 ) = 3 ，类似地可得矛盾! 情形1 3i u l 地i ) = i o l i 1 ，2 ，3 ，4 ，5 h i = 1 不妨设f ( w n 锄) = i o ，由于是邻 点可区别正常边染色，于是有，如1 2 奶3 ) = ，( 抛t l j 2 3 ) = ，( 嘶4 t l ，1 5 ) = ，吻5 ) = o ，类 似于情形1 2 ，若，( t i l l 叫1 2 ) = 1 ，则，舢1 2 地2 ) = 2 或3 ( 不妨取2 ) ，必有，( 坳l t i j 2 2 ) = 3 ，( 1 l 1 5 ) = 3 ，f ( w 1 5 地5 ) = 2 ，( t l j 2 l i 2 5 ) = 1 ，则g 和1 1 ) = c ( 毗1 ) ，矛盾! 若 f c 1 2 t j 2 2 ) = 3 ，类似地得矛盾l 故断言1 为真 断言2 某种颜色如染了3 条边，其余颜色各染了4 条边 2 r 。r 和p 竹。kc k 的郐点可区别正常边染色 证明由断言1 及i 曰( 恳岛) ) i = 1 5 知，有6 个点的颜色集合中出现了颜色如，其余 四个点的颜色集合中无南 由于，是邻点可区别正常边染色，这四个点必构成独立集，而在g 上不存在3 个点 的独立集，则必有两个点在圈铆l 铆2 7 3 ) 1 3 叫1 4 t o l 5 n 上，不妨设为铆2 ，叻4 ，另两个点在圈 讹1 t 1 2 2 1 l j 2 4 t c j 2 5 叻l 上，且必为地l ， 1 0 2 3 这样必有边1 0 1 5 训2 5 与这四个点不关联则如染 的三条边必为叫l l t j 1 5 ，埘1 5 毗5 ，u 1 2 5 t j 2 4 ，但这三条边构成条路，不是匹配矛盾! 因此，垃( b x 岛) 25 下证bx 魄存在5 一a v d p e c ，定义映射f ： ，( 脚n 1 2 ) = i ( 0 ；1 4 1 1 ) 1 5 ) = ，( t i j 2 4 t 也5 ) = 1 ， f ( w n t l ，2 1 ) = ，1 2 t 坳) = f ( w 2 s v 【j 2 4 ) = 2 ， ，( 们1 3 埘1 4 ) = ，( ”1 l 1 5 ) = ，( 坳l u 恤) = 3 ， ，( t c j l 2 呦) = f ( t c j 2 2 w 2 3 ) = f ( w l s 劬s ) = 4 ， ，( t l j l 3 ) = ，扣1 4 u 】2 4 ) = ，( t c j 2 1 t 啦5 ) = 5 易验证，是岛侥的5 一a v d p e c 综上所述，定理2 2 得证 6 3 磁, - f 染色 在这一部分，我们引入了磁的定义，给出了璐的邻点可区别正常边色数 定义3 1 设r = t ，l 抛表示n 个顶点的路，将r 中距离为k ( 2 七n 一2 ) 的任两顶点用一条新的边连起来所得到的图称为路r 的七次方，记作磺 定理3 1 设r = 印l 0 2 ，则 s 2 ，= ki 0 证明设s ( 瑶) = 1 ，2 ，3 ，4 ，5 分两种情形考虑： 情形1 ：n = 4 ，5 时，有相邻最大度为( = 3 ) 的点或有唯一最大度为( = 4 ) 的点， 由引理i i 有疋( p 。_ 2 ) 4 ，因此仅需证焉有4 一a v d p e c 如图1 ，2 所示： 仁皇扛9 驾至莛抽 图1n = 4图2 n = 5 显然是砰，瑶的4 一a v d p e c ： 情形2 ：n 6 时，有相邻最大度为( a = 4 ) 的点，由引理1 1 ，有死( 焉) 4 ，因此仅 需证磲有5 一a v d p e c ，构造如下的染色法： 边w l j 2 ，r a y 4 ，地优+ l ，一1 依次用颜色1 ，2 循环去染；距离为2 的 边”l 地，r a y 5 ，地“一1 ) + 1 ，v 2 i + l ，( i = 1 ，2 ，【孚】) 依次用颜色3 ，4 ，5 循环去 染；边v 2 v 4 ，地，地。一1 ) + 2 t 嘲_ 2 ，a = 1 ，2 ，【孚】) 依次用颜色5 ，3 ，4 循环去 染易验证该染色是正常的，且在该染色下，0 似) ，0 h ) ，d ( 一2 ) 依次循环地等于 5 ) ， 4 ) ， 3 ) 此外，d ( v 1 ) d 她) d ( 强) ，d ( ) d ( 一1 ) d ( 一2 ) ，因此是焉( n 6 ) 的一个5 一a v d p e c 定理3 2 设r = 仇现，n 4 ，七3 ，则 f 3 ， k = n _ 2 x ：( 磁) = 4 ，与量ks ，l 3 ； 【5 ，k 警 证明设s ( 磁) = t 1 ，2 ，3 ，4 ，5 ) ，分三种情形考虑： 情形1 ：当七一n 一2 时，磁有不相邻的最大度( z x = 3 ) i j , 点，由引理1 1 ，仅需证璐 有3 一a v d p e c ，构造如下的染色法 当n 兰o ( m o d 3 ) 时，边t h t j 2 ，t j 2 地，q 哦+ 1 ，一l 依次用颜色1 ，2 ，3 循环去染： 边1 ) 1 1 ，l ，v 2 1 7 b + 2 用颜色3 去染 7 3 罐的邻点可区别正常边染色， 当ne1 ( r o o d 3 ) 时，边口l 啦，t j 2 强，q 姚+ “， o n 一2 一l 依次用颜色1 ，2 ，3 循环 去染，且此时边一2 一1 已着颜色2 ；边一1 用颜色1 去染；边1 + l ， 0 2 v k + 2 用颜色3 去染 当ne2 ( r o o d 3 ) 时，边研抛，t j 2 ，q 哦+ l ，一1 依次用颜色1 ，2 ，3 循环去 染：边”l 垤+ l 用颜色2 去染；边t j 2 珧+ 2 用颜色3 去染 易验证上述染色是璐伪= n 一2 ) 的一个3 一a v d p e c 情形2 ：当翌s 七s ，l 一3 时，璐有相邻最大度为( = 3 ) 的点或有唯一最大度为 ( = 4 ) 的点，由引理1 1 ，仅需证磁有4 一a v d p e c ，构造如下的染色法分两种情形： 情形2 1 ：七= 堡丢 当七eo ( m o d s ) 时，边仇t j 2 ，t j 2 t j 3 ，一，t “卜卜1 ；v k + 2 v k + 3 ，_ t ) k + 3 v k + 4 ，一i v 依次用 颜色1 ，2 ，3 循环去染；边t ，蚪1 + 2 用颜色4 去染；边仇坼1 ，坼l t + 1 依次用颜色2 ，1 去染； 边t j 2 珧+ 2 用颜色3 去染；边t v k + s ，v 4 v k + 4 ，雠地k 用颜色4 去染易验证该染色是正常 的，且在该染色下，0 他) = 4 ) ，o ) 0 帆) ，e ( ) ，0 ( 蚪2 ) ，0 ( + 3 ) ，0 ( 站) 依次循环地等于 1 ) ， 2 ) ， 3 ) 当k ；1 ( m o d 3 ) 时，边t ，1 吨，t j 2 地，吨仇+ l ，一1 依次用颜色1 ，2 ，3 循环去 染；边u l 讥+ 1 + 1 t + 1 依次用颜色3 ，4 染；边t j 2 他+ 2 ，t j 3 雠+ 3 ，地仇“，- - ，t 用颜色4 去染易验证该染色是正常的，且在该染色下，0 池) = 3 ) ，0 沁) ，d 帆) ，0 ( 仇) 依次 循环地等于 1 ) ， 2 ) ， 3 ) ；0 ( 。) ，o ( + s ) ，口( 啦k ) 依次循环地等于 1 ) ， 2 ) ，( 3 ) 当七e2 ( r o o d 3 ) 时，边”1 t 1 2 ，t b 地，t b 讥；r e ，蜥，2 + 3 ；“，讥* v 蚪6 ，一， 一1 依次用颜色1 ，2 ，3 循环去染；边啦，仇+ 3 喉“，t j 2 讥+ 2 ；佻饥+ 6 ，嘶+ 7 ，t 用颜色4 去染；边_ l ，l i ，坼1 t + l 依次用颜色3 ，4 去染；边地坼3 ，t 7 4 仇“，5 依次用颜色1 ，2 ，3 去染易验证该染色是正常的，且在该染色下， 0 ( 地) = 3 ) ，0 ( j 3 ) = 4 ) ，0 ( 啦+ 5 ) = 4 ) ；0 ( 也) ，0 似) ，0 ( ) 依次循环地等 于 1 ) ， 2 ) ， 3 ) ；0 ( 他牡) ，0 他舳) ，o 帆“) ，d ( 啦十6 ) ，o ( t 1 2 ) 依次循环地等于 1 ) ， 2 h 3 ) 此外，在上述染色下有d h ) d 她) ，吐( ) d ( 一1 ) ，因此是磺( n = 2 k + 1 ) 的一个 4 一a v d p e c 情形2 2 ：；七n 一3 当七= 3 ，竹= 6 时，如图3 所示： 显然是罐的4 一a v d p e c 8 3 露的邻点可区别正常边染色 当k 4 ，n 7 时，边忱t j 2 ，1 j 2 魄，i j i i + 1 ，一1 依次用颜色1 ，2 ，3 循环去染； 边忱+ l ，也1 j 2 “，地+ 3 ，讥t j 2 t 用颜色4 去染易验证该染色是正常的，且在该染色下， 当n = 2 k 时，有0 池) ，0 ( t j 3 ) ，0 ( k ) 依次循环地等于 3 ) ， 1 ) ， 2 ) 此外，在上述染 色下d ( v 1 ) d 沁) ，d ( ) d ( 一1 ) ，因此是磁伽= 2 七) 的一个4 一a v d p e c 当n 2 k 时，同上可验证该染色是磁忙+ 3 t l ，0 ( 姐) = 3 ，4 ) ，o ( ) = l ，5 ) ；0 ) ，d ( 嘶) ，一，0 ( ) 依次循环地等于 2 ，4 ) ， 3 ，4 ) ， 1 ，4 ) ；0 ( t 1 ) = 3 ) ，0 ( + 2 ) = 1 ) ，0 ( + 3 ) = 2 ，5 ) ；0 ( 十4 ) = 2 ，4 ) ，0 h + 5 ) = 2 ，5 ；口( + 6 ) ，e ( + 7 ) ，0 ( ) 依次循环地等 于 3 ，4 ) ， l ，4 ) ， 2 ，4 ) 此外，在上述染色下d h ) p q 1 ，则疋( 一朋) = m + n + p 定理4 2 设n 2 ，则娃c l 1 。1 ) = 7 1 + 3 证明由引理1 1 及引理4 1 ，仅需证k 、l ，1 1 有m + 3 ) 一a v d p e , g 设s ( f 。, l , x , x ) = 1 ，2 ，n + 2 ，o ) ，构造映射，：e ( 珞i l l ，1 ) 一 1 ，2 ，n + 2 ，o 如下：( 以下均在模n - t - 3 下取值) ，( m l t j 3 1 ) = 1 ，( 拙l t l 2 1 ) = 2 ，f ( 蛳l v l , ) = i + 2 a = 1 ，2 ，一，n ) ； ，( 协1 啦! ) = 3 ，( 1 j 3 l t j l ) = i + 3 ，( 地l t ，1 t ) = f + 4 a = 1 ，2 ，竹) 对，有0 她1 ) = 4 ) ，0 h 1 ) = 2 ，口( u 4 1 ) = o ) ；且d h t ) n 2 ，则疋( 1 ，1 ) = m + 竹+ 2 证明由引理1 1 及引理4 1 ，仅需证1 1 有( 仇+ 礼+ 2 ) 一a v d p e c 设s ( k 。 1 1 ) = l ，2 ，m + n + l ，o ，构造映射f ：e ( k 。m 1 ，1 ) 一 1 ，2 ，m + n + l ，o ) 如下：( 以下均在模m + n + 2 下取值) ，似l 协1 ) = 1 ，f ( v 4 1 v 2 ) = i + 1 ( i = 1 ，2 ，由，( 啦! 奶j ) = n + i + 1 a = 1 ，2 ，m ) ； ，( t 】3 1 t 憾) = i + 2 ( i = 1 ，2 ，让) ，( 如l t ，l i ) = n + i + 2 a = l ，2 ，- ，m ) ， ，( 呦饥j ) = n + i + j + 2 a = 1 ，2 ，一，m ；j = 1 ；2 ，佗) 1 0 54 完全垂部图的邻点可区别正常边染色 对 有0 ( 地1 ) = 2 ) ，口( 蛳1 ) = o ) j t d ( v l i ) d ( t ) 0 = 1 ，2 ，一，m ；j = l ，2 ，n ) ，因此，是，n ，1 ，1 的一个( m + n + 2 ) 一a v d p e c ，定理得证 定理4 4 若礼p + 2 且p 2 ，则 毛( ，。p ) = 3 n 证明由引理1 1 及引理4 1 ，仅需证瓦 n ，。，p 有3 n a v d p e c 设s ( 。 p ) = 1 ，2 ，3 n 一1 ，o ) ，构造映射，：e ( 。，p ) 一 l ，2 ，3 n l ，o ) 如下( 以下均在模3 n 下取值) ： y ( v 4 蛳) = i + j l ，i ( v 4 帕) = n + i + j i ，( i = 1 ，2 ，一，p ；j = l ，2 ，一，n ) ； y ( v 4 1 v u ) = 2 n + t + j 一1 ( i = 1 ，2 ，- ，p ；j = 1 ，2 ，- - ，住) ； $ ( v 3 1 v 2 j ) = n + p + + j 一1 ，$ ( v 3 1 v l j ) = p + i + j i ，( i ，j = 1 ，2 ，一，n ) f ( 地i v u ) = 2 n + p + i + j 一1 ( i ，j = 1 ，2 ，一，n ) 对，有o ( v “) = ( n + p + i ，n + p + i + 1 ，2 n + i 一1 ) ，0 ( ) = p + ，p + + 1 ，一，n + i 1 ) ，0 ( v s i ) = 2 n + p + i ，2 n + p + i + 1 ，一，3 n + 一1 ) ( i = 1 ，2 ，一，p ) ； r d ( v 4 j ) d ( v 3 i ) = d ( ) = d ( 1 i ) ，( i = 1 ，2 ，n ；j = 1 ，2 ，功因此，是 ，t l l p 的 一个3 n a v d p e o ，定理得证 定理4 5 若n p + 1 且p 1 ，则 疋( f 矗，n i p ，p ) = 2 n + p + 1 证明由引理1 1 及引理4 1 ，仅需证，。有( 2 n + p + 1 ) 一a v d p e g 设s ( ”) = 1 ，2 ，2 n + p ，o ) ，构造映射，：e ( ，。p ，p ) 一 1 ，2 ，2 n + p ，o ) 如下( 以下均在模凯+ p + 1 下取值) ： ，( 哂) = i + j 一1 ( i ，j = 1 ，2 ，p ) ； ，( 锄t ) = p + i + j 一1 ，( ”u ) = n + p + i + j l ( i = 1 ，2 ，一，p ；j = 1 ，2 ，哟； ，( 地i t 协) = n + p + i + j ，( u 玎) = p + i + j 一1 ( i = 1 ，2 ，- 一，p ；j = 1 ，2 ，一，n ) ； i ( v 2 i v u ) = n + 2 p + i + j 0 ，j = 1 ，2 ，一，n ) 对，有0 ( v l i ) = 2 p + i ，2 p + i + 1 ，n + p + i l ；n + 印+ i ) ，0 ( 也t ) = 2 p + i ，2 p + i + 1 ，- ，n + p + 0 0 = 1 ，2 ，- - - ，n ) ；0 ( ) = n + p + ) ，0 ( m i ) = a 一1 ) ( i = 1 ，2 ，- ，p ) 因此，是m 即的一个( 2 n + p + 1 ) 一a v d p e g ，定理得证 定理4 6 若n p + 2 且p 2 ，则 x ：( p m ) = n + 劫+ 1 1 1 4 完全4 - 部图的邻点可区别正常边染色 证明由引理1 1 及引理4 1 ，仅需证j 0 m 1 p 有+ 2 p + 1 ) 一a v d p e c 设s ( 玩m 口) = 1 ，2 ，礼+ 2 p ，o ) ，构造如下映射f ：e ( 墨。m p ) 一 l ，2 ，礼+ 2 p ，o ) 分两种情形考虑( 以下均在模n + 2 p + l 下取值) ： 情形1n p eo ( m o d 2 ) i ( v 4 1 v 3 j ) = i + j 一1 ( i ，j = 1 ，2 ，p ) ； 地i ) = 字+ + 卜1 ( t ，j = 1 ，2 ，p ) ； f ( v 4 ”u ) = n 1 + 一3 p + t + j 一1 0 = 1 ，2 ，一，p ；j = 1 ，2 ，一，t n + p + 1 ) f ( v 4 1 v l u + 2 笋+ 1 ) ) 2 p + i + j “= 1 ，2 ，p ；j = 1 ，2 ，t n - p 一1 ) ，( n p 4 时，用此式) ； 舳脚) = 学+ 瓴j _ l 2 ，p ) ； f ( v a l ) = 学+ t + j ( i = 1 ，2 ，p j = l ，2 ，t n - - p 1 ) ( 札一p 4 时，用此式) ； f ( v 3 , + 警叫) = p + 一1 ( i = 1 ，2 ，i p j = l 加，字+ 1 ) f ( v 2 i v l j ) = p + i + f f ( i = 1 ，2 ，p j - 1 2 ，字一1 ) ， 一p 4 时，用此式) ； f ( v 2 i t ) l ( j + 竿一1 ) ) = i + j 一2a = 1 ，2 ，一，p ；j = 1 ，2 ，一，p + 2 ) ； f ( v 2 i v l 字+ 1 ) ) = 学+ ( t _ 1 ，2 ，删j _ 1 2 ，t n - p 一1 ) 情形2n p el ( m o d 2 ) 一p 4 时用此式) f ( v 4 1 j ，j 3 j ) = i + j 一1 ( ，= 1 ，2 ，一，p ) ； f ( v 4 t ) = 生乒4 - i + j ( i ，j = l ，2 ，p ) ； ，( 啦；”，j ) = 掣+ + 丘。= 1 ，2 ，p ；j = 1 ，2 ，一，兰詈盟) ，( 口l 叶掣) ) 2 pq - i + j o = 1 ，2 ， m 孤) = 掣+ “j _ 1 1 2 ， ，( 1 j ) = n + t s p 一+ l + i + j ( 江1 ，2 ，p ；j = l ，2 n p 一1 、 广一 n p 一3 、 丁j m p 5 时，用此式) ； i ( v 3 1 v l ( j + 字) ) ：p + 一l ( 渊，2 ，j 钆2 ，生字) f ( v 瓤v l j ) ：p + + j + 1a = 1 ，2 ，一，p ；j = 1 ，2 ，兰二乒) ， m p 5 时，用此式) ； i ( v 蕊v l u + 字) ) = + j 一1 a = l ，2 ，一，p ；j = l ，2 ，p + 2 ) ； 瓶+ 掣炉n + 5 厂p + lm 巾_ 1 2 ，p 渊，2 ，半) 对| 南 n - - p 三o ( m o d 2 ) ，。( 啦；) = 学+ 垧) = o l ， 0 ( ) = 扣+ ) a = 1 ，2 ，p ) ； n p - - l ( m 。d 2 ) ，。( 吨；) = 掣+ i ) ，。( ) = i 一1 ) ， 0 0 4 ) = p + q a = 1 ，2 ，一，p ) 此外，d ( l j ) d ) = d ( 地i ) = d ) ( j = 1 川2 一，n ； = 1 ，2 ，p ) 因此，是口 的一个+ 2 p + 1 ) a v d p e c ，定理得证 定理4 7 若，i 2 ，则 x ：( 凰。，1 ) = 3 n 证明由引理1 1 及引理4 1 ，仅需证，n 。一1 有3 n a v d p e c 由引理4 2 及 引理4 3 ，厩 一1 有3 n e p e c ，而邶，n - 1 的边数恰能被3 n 所整除，所以每种 色恰染了2 n 一1 条边且这3 r d 牛色在顶点v 4 1 ( i = 1 ，2 ，n 一1 ) 上都表现了，每个顶 点，v 2 i , 蛳u = 1 ，2 ，n ) 上均有一种色未表现，不妨设t 色在顶点 l 上未表现，则必在 其它所有顶点上表现了，否则与。，1 有3 n e p e c 染色矛盾! 因此，是编，n ，。，1 的一个3 n a v d p e c ，定理得证， 4 完全4 - 部图的邻点可区别正常边染色； 定理4 8 若n 3 ，则 x ：( p 1 p l ”1 ) = 3 n 一1 证明由引理1 1 及引理4 1 ，仅需证甄，n - l p l ，l 有( 3 n 一1 ) 一a v d p e c ， 设s ( 珞p 1 ，n - 1 ) = 1 ，2 ，3 n 一2 ，o ) ，构造映射，：e ( k n n - l l ，n - 1 ) 一 1 ，2 ，3 n 一2 ，o ) 如下：( 以下均在模3 n 一1 下取值) ，( ) = i + j 一1 ，f ( v 4 i v 2 1 ) = n + i + j 一2 ( i ，j = 1 ，2 ，一，r | 一1 ) ； f ( v 4 1 v l j ) = 2 n + i + j 一3 ( i = 1 ，2 ，一，n 一1 ；j = 1 ，2 ，一，礼) ； ，( 均) = 2 n + i + j 一2 ( i ，j = 1 ，2 ，一，n 一1 ) ， 贰l 。亳 f ( v 3 i v l l ) = t 一1 ( i = 1 ，2 ，一，n 1 ) f ( v 3 v l j ) = n + i + 歹一2 0 = 1 ，2 ，一，n 1 ；j = 2 ，- 一，n ) f ( v 2 i v n ) = n + i 一2 0 = 1 ，2 ，n 一1 ) ， ，( l j ) = + j 一3 ( i = l ，2 ，- 一，n 一1 ；j = 2 ，n ) 0 ( 砚 ) = 2 n + i 一2 ) ，0 ( ) = n + i 一1 ) 0 = 1 ，2 ，一，扎) c ( v 4 | ) = a 1 ) g = 1 ，2 ，n 1 ) 此外，d m j ) ( d ( v 2 f ) = d ( v a i ) = d ( v 4 ) u = 1 ，2 ，n = l ，2 ，f l 一1 ) 因此，是 琏p 1 ，。_ 1 ，。一l 的一个( 3 n 一1 ) 一a v d p e c ，定理得证 定理4 9 若n p + 1 且p q + 1 ，则 x ：( ，。舢) = 2 n + p 证明由引理1 1 及引理4 1 ，仅需证噩b 。m 有( 2 n + p ) 一a v d p e c 设s ( 风，。 口) = l ，2 ，2 n + p 1 ，o ) ，构造映射，：e ( 。，p 口) 一 1 ，2 ，2 n + p 一1 ，o ) 如下( 以下均 在模( 2 n + p ) 下取值) ： ，( 蛳i ) = i + j 一1 ，a = 1 ，2 ，一，g ；j = 1 ，2 ，一，； ，(