（应用数学专业论文）图的三类染色及其概率方法.pdf

摘要 本文通过归纳定义了图的三类染色一无圈染色，邻点可区别的染色和点可区别 的染色应用l o v d s z 局部引理的赋权形式，讨论并得到了任一最大度4 的图g ，其 邻点可区别的无圈边色数至多为1 6 a 2 应用l o v 6 s z 局部引理的一般形式，讨论并得 到了任一最大度3 2 2 i n 5 ，最小度j 3 2 以至五五的图g ，其邻点可区别的全色数至 多为2 + 1 + 2 以至i 五；进一步，若全色数( g ) a + 2 ，则其邻点可区别的全色数至 多为+ 2 十2 以i 面五然后，通过具体构造染色的方法讨论并给出了路、圈、完全 图、星、扇、轮的m y c i e l s k i 图，路与圈的联图p mv 岛的点可区别的全色数 关键词：局部引理；邻点可区别的无圈边染色；邻点可区别的无圈边色数；邻点 可区别的全染色；邻点可区别的全色数；点可区别的全染色；点可区别的全色数 a b s t r a c t i nt h i sp a p e r ，b yi n d u c t i o nw ed e f i n et h r e ek i n d so fc o l o r i n g so fg r a p h s ，w h i c ha l e a c y c f i cc o l o r i n g ， a c e n tv e r t e x - d i s t i n g u i s h i n gc o l o r i n ga n dv e r t e x - d i s t i n g u i s h i n gc o l o r - 7， i n g w i t ha p p l y i n gt h ew e i g h t e df o r mo ft h el o v 缸zl o c a ll e m m a w eh a v ed i s c u s s e da n d o b t a i n e dt h a tt 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 ga c y c l i ce d g ec h r o m a t i cn u m b e ri sa tm o s t 1 6 a 2f o ra n yg r a p hgw i t hm a x i m u m d e g r e ea 4 w i t ha p p l y i n gt h eg e n e r a lf o r mo ft h e l o v 矗s zl o c a ll e m m a ，w eh a v ed i s c u s s e da n do b t a i n e dt h a tt 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 ri sa tm 0 8 t2 + 1 + 2 、1 af o ra n yg r a p hgw i t hm a x i m u m d e g r e ea 3 2 2l n5a n dm i n i m n n * ld e g r e ej 3 2 面；f u r t h e r m o r e ，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 gt o t a lc h r o m a t i cn u m b e ri sa tm o s t + 2 + 2 l n i ft h et o t a lc h r o m a t i c n u m b e rx t ( g ) s - 4 - 2 t h e nw i t hg i v i n gc o l o r i n g so fag r a p h ，v 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 so nm y c i e l s k i sg r a p h so fp a t h ，c y c l e ，c o m p l e t eg r a p h ，s t a r ，f a na n d w h e e l r a n dv 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 so fp zv a r ed i s c u s s e da n d g i v e n ，r e s p e c t i v e l y k e y w o r d s ：l o c a ll e m m a ；a d j a c e n tv e r t e xd i s t i n g u i s h i n ga c y e 5 ce d g ec o l o r i n g ； a d j a c e n tv e r t e xd i k c i n g u i s h i n ga c y e f i ee d g ec h r o m a t i cn u m b e r ；a 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 ；a 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 ；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 ；v 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 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包含为获得西北师范大学或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并 表示了谢意。 签名： 笺豳纭 日期：兰翌翌兰丝 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、 交论文的复印件，允许论文被查阅和借阅； 采用影印、缩印或其他复制手段保存论文。 签名：篓豳! 纭 导师签名 使用学位论文的规定，即：学校有权保留送 学校可以公布论文的全部或部分内容，可以 ( 保密的论文在解密后应遵守此规定) 铒逝 日期2 c 碲毛i 三扣毛 王_ 一 刖口 图的染色问题是n p 完全问题，是图论的主要研究内容之一染色的基本问题就是确定 其各种染色法的色数四色猜想首次在点染色中提出，从而使图论染色理论的研究工作得 以发展之后，许多数学工作者都致力于点染色，边染色 2 2 6 1 的研究1 9 7 3 年，g r i i n b a u m 【5 l 首次提出了图的无圈点染色，a l o n 和j e n s e n 等在 6 ，4 6 l 中对无圈边染色，无圈点染色作 了进一步的讨论1 9 9 3 年，b u r d sm 介绍并研究了点可区别的边染色( 或称强边染色，或 称o b s - 染色) ，s c h e l p ，c e r n 5 7 ，h o 面a k 和s o t 直k 等在 2 s 一3 6 】中作了更深入的研究，得到了一些 好的结果2 0 0 2 年，张忠辅【，1 首先提出了图的邻点可区别的边染色( 或称邻强边染色) 问 题，掀起了图论染色问题研究的一股热潮，现在也已经得到很多有价值的成果【1 1 1 3 】，【3 7 4 0 1 对于在图的点染色和边染色的基础上产生的图的全染色【4 1 4 5 】问题的研究，许多结果 也已经陆续出现然而，就点可区别的全染色问题而言，鉴于其存在的困难，现在所作的工 作很少2 0 0 4 年，在全染色的基础上，相对于图的点可区别的全染色，张忠辅【q 又提出了邻 点可区别的全染色等一系列新概念，使得图论界产生了许多更有趣的问题 本文第二部分在传统的三类染色一点染色，边染色，全染色的基础上，通过将点，边归纳 为元素，相应定义色集合，通过附加一定的条件，定义了三类染色：无圈染色，邻点可区别染 色和点可区别染色使得对附加一定条件的所有染色的定义具有关联性和统一性，从而便 于以后的研究和推广本文第三、四、五部分对这三类染色之下的三部分子问题：邻点可 区别的无圈边染色，邻点可区别的全染色和特殊图的点可区别全染色分别进行了探讨 概率方法是一种用来证明具有某些特定属性的目标存在性的技巧，在很 多领域中都发挥着日益重要的作用，尤其是在图的染色方面从1 9 4 7 年p a u le r d 6 s 在r a m s e y 数r ( ，) 2 6 的证明中首次引入概率方法，到2 0 0 2 年国际数学家大会上n o g a a l o n 作了有关图的概率方法的- - 4 , 时报告，这个新颖，活跃的研究领域正受到国际数学界 的普遍关注l o v g s z n 部引理，作为概率方法中核心部分之一，是证明具有某些特定属性的 目标的存在性的一个非常重要的工具它的优点是我们只需证明具有某些特定属性的目 标存在的概率值大于0 即可，即使这个概率值非常小正因为如此，我们研究的图类就扩展 t u - j m 以很大并且无结构性的随机图中引理的证明很短，但发挥的作用却非常大相关应 用参见文献1 3 】， 4 1 ， 1 0 一1 4 1 ， 1 7 - 2 3 1 前言 对于邻点可区别的无圈边染色涨忠辅等人首先提出这一新概念，并且在【8 】中通过用 分析的方法得到了，。，殿，砩，c 尝等图的邻点可区别无圈边色数，至今还没有出现用 概率方法研究的结果本文在第三部分中，通过尝试应用概率方法，讨论了最大度满足一定 限制条件的任意图g 的邻点可区别的无圈边染色，得到了其色数的一个上界 对于邻点可区别的边染色，用概率方法( 或分析方法) 得到了一些很好的结果 如a k b a r i ，b i d l d a o r i 和n o s r a t i 在文【1 0 】中得到：对任一无孤立边的图g ，其邻点可区别的边色 数屯( g ，1 ) 3 a b a j i s t e r ，g y s r i ，l e h e l 和s c h e l p 在文 n i c e 得到：若图g 没有孤立边，则邻点 可区别的边色数x 2 a + o ( 1 0 9 x ( g ) ) g h a n d e h a r i 和h a t a m i 在文【1 2 】中得到：若图g 是 简单图，最大度a 1 0 6 , 则邻点可区别的边色数x ：( g ，1 ) + 2 7a d z - i - s h a t a m i 又 在文【1 3 】中得到：若图g 没有孤立边，最大度a 1 0 2 0 ，则邻点可区别的边色数x 0 兰 + 3 0 0 而邻点可区别的全染色用概率方法得到的结果很少，且得到的界一般很大如刘 信生等人在文【1 4 】中得到：对任一最大度为的图g ，其邻点可区别的全色数。( g ) 3 2 a 本文在第四部分中，通过尝试应用概率方法，讨论了最大度，最小度( 以及全色数) 同时满足 一定限制条件的任意图g 的邻点可区别全染色，得到了其色数的一个较小的上界 1 9 5 5 年，m y c i e l s k i 1 l 构造了一种最简单的图( 称为m y c i e l s k i 图) 证明了：存在任意 大( 点) 色数的无三角形图之后，m y c i e l s k i 图引起了许多学者浓厚的研究兴趣，得到了 一系列好的成果如文【1 6 】中对于路、圈、完全图、完全二部图、星、扇、轮等特殊图 类，得到了其m y c i e l s k i 图的邻点可区别全色数但点可区别的全染色，比邻点可区别的 全染色研究难度大，现在得到的结果较少本文在第五部分中，讨论了路、圈、完全图、 星、扇、轮的m y c i e l s k i 图的点可区别全染色，路与圈的联图岛。vr 的点可区别的全染 色，得到了其具体的色数， 在本文中所讨论的图均为有限图对于标准的图论记号可参看【1 】， 2 5 1 ，【4 7 】和【4 8 】 2 1 预备知识 在这一节中我们给出一些与本文相关的基本概念，原理和引理详细内容请参阅所列 定义1 1 对n o ( v , e ) ，映射f ：v ( c ) 一 1 ，2 ，) 满足对任意相邻的顶 点u ，”，有f ( u ) ，( ”) ，则称，是g 的一个女一正常点染色，简记作一p v c ，且称) ( g ) = m i n k l c 有k 一正常点染色 为g 的点色数【1 1 对图g ( v e ) ，映射f ：e ( g ) 一 1 ，2 ，) 满足对任意相邻的边e l ，e 2 ，有f ( e 1 ) ，( e 2 ) ，则称，是( ? 的一个k 一正常边染色，简记作一p e c ，且称x 7 ( g ) = m i n k g ：n k 一正常 边染色，为c 的边色数吵 对图g ( v e ) ，映射f ：v ( c ) u e ( c ) 一 1 ，2 ，- ，) 满足1 ) 对任意，v w e ( g ) ，u ，有，( ) ，( ”) ；2 ) 对任意“”e ( g ) ，有，( u ) ，( ”) ，f ( u ) f ( u v ) ，f ( v ) f ( u v ) ，则称，是g 的一个一正常全染色，简记作k p t c ，且称始( g ) = m i n k l c 有k 一正常 全染色1 为g 的全色数【2 1 定义1 21 3 1 将随机试验e 的所有可能结果组成的集合称为目均样本空间，记为q ； q 的一个子集a 称为事件；有限概率空间( n ，只) 是由一个有限的样本空间q 和概率 函数只：q 一【0 ，1 】，满足以下几点：( 1 ) 只( z ) = 1 ；( 2 ) p r ( a ) = p r ( z ) ；( 3 ) 令a = q a ，n p ，( i ) = 1 一只( a ) ；( 4 ) 只( a u b ) = p r ) + p r ( b ) 一只( a n b ) ；( 5 ) p ，( a ub ) sb ( a ) + p r ( b ) ，更一般地，p r ( ua t ) s p d a ) ，称为概率的次可加性 i = li = l 定义1 , 3 对于n 的每个，有耳( z ) = 南，称为均匀分布；n 中的一个均匀元素是一 1 个随机元素，每个概率均是相等的 定义1 4 吲如果事件a 发生的概率不受事件b 的影响，称事件a 对事件b 是独立 的；对n 个事件a l ，a 2 ，a 。，若对v a ，a j 0 j ， ，j = l ，2 ，n ) 有只( a n a ) = 只( a ) 只( ) 成立，称事件a - ，a 2 ，厶n 两n a ；对n 个事件a ，a 2 ，a n ，若对事件 l 的任意子集 a l ，a 2 ，a ) ，有只( a 。ina ) = 鼻( a 1 ) ，称事件a 1 ，a 2 ，a 。互相独立 i = 2 3 1 预备知识 定义1 5 嘲令a 。，a 2 ，几为概率空间的n 个事件，对事件的集合s ，丁是s 中一些事 件( 或事件的补) 构成的任一子集，如果满足只( a ln ，) = 只( a ) ，则称a 与事件的 a j e t 集合s 互相独立；以y ( h ) = l ，2 ，n ) 为顶点的有向图h = ( y ( 日) ，e ( h ) ) 被称作相关 图e 如果对所有 a 。：lsi 墨n ) ，a 与集合 a j ：( i ，j ) 荜e ( 圩) ) 中的事件互相独立 引理1 1 ”1 ( 第一矩量原理) 如果e 啤) t , n p ，( x t ) 0 。 注：多应用于x 是正整数值b e ( x ) 0 引理1 2 4 1 ( 互相独立原理) 假设) ( = x 1 ，x 2 ，是独立随机试验的序 列，妒= a - ，a z ，一。) 是事件的集合，对每个月t ，都存在r x ，每个a 被r 决定，如 果e n ( 乃。，乃：，- ，日。) = 咖，那么 与 a a j 一，a j 。) 互相独立 l o v g s z 局部引理主要用来证明具有某些特定属性的目标的存在性问题在实际遇到的 问题中，经常会出现事件之间相互依赖的情况，这时候，如果依赖的数量被充分地限制，我 们仍可断定成功的概率为正下面给出本文用到的l o v a s z 局部引理的赋权形式和一般形 式，还有其它形式参见【4 】 引理1 3h ( 赋权局部引理1 考虑( 典型的坏的) 事件的集合e = a 1 ，a 2 ，凡) ，对每一个a ，都存在d i ( b 可以 空) ，使得每一个a 。与一( nu a t ) 互相独立( 对某个n e ) 如果有整数1 ，t 2 ，t 。 1 和实数0 p v 4 使得对每个1s i 仉有( a ) 只( a ) 矿，( b ) ( 2 p ) o t d 2 ， 则e 中所有事件都不发生的概率是正的 引理1 4 叫( 一般局部引理) 考虑( 典型的坏的) 事件的集合= a ，a 。，a 。) ，对每一个a ，都存在耽( d , - i d a 空) ，使得每一个a 与e 一( d iua ) 互相独立( 对某个d i e ) 如果有实数z 1 ，z 2 ，z 。 【0 ，1 ) 使得对每个1 i n ，b ( a t ) 茎轨n ( 1 一巧) ，则e 中所有事件都不发生的概率至 】e d t n 少是n ( 1 一。，) 0 4 52 图的三类染色 f i o r i n i ，w i l s o n ，h a n s e n ，m a r c o t t e ，k r o n k 和m i t c h e m 等人于1 9 7 3 年至1 1 1 9 9 9 年分别在 2 4 - 2 6 1 中对点染色，边染色作了全面而深入的研究1 9 7 3 年，g r i i n l y a u m n 首次提出了图的 无圈点染色，a l o n 和j e n s e n 等在【6 ，4 6 1 中对无圈边染色，无圈点染色作了进一步的讨 论1 9 9 3 年，b u r r i s 【2 介绍并研究了点可区别的边染色( 或称强边染色威称o b s 一染色) ， s c h e l p ，e e r n ，h o r f i 丘k 和s o t g k 等在 2 8 - 3 6 1 中作了更深入的研究，得到了一些好的结果 2 0 0 2 年，张忠辅【7 j 首先提出了图的邻点可区别的边染色( 或称邻强边染色) 问题，目前也已经 得到很多有价值的成果 1 l 一1 3 1 ， 3 7 - 4 0 1 对于在图的点染色和边染色的基础上产生的图的 全染色 4 1 4 5 问题的研究，y a p ，k o s t o c h k a ，h i l t o n ，h i n d 等已经陆续得到许多结果然而，就 点可区别的全染色问题而言，鉴于其存在的困难，现在所作的工作很少2 0 0 4 年，在全染色 的基础上，相对于图的点可区别的全染色，张忠辅1 9 1 又提出了邻点可区别的全染色等一系 列新概念 在对上述各种染色的概念深入分析之后，我们通过归纳概括，从而给出图的三类染色 的定义 为此，首先对上面三种传统染色( 点染色，边染色，全染色) 可归纳为： 对图g ( u e ) ，把点 y ( g ) ，边e e ( g ) 可看作g 中的元素，记为n g 在，：g 一 1 ，2 ，) ( 即：，：v ( c ) 一 1 ，2 ，) ，或，：e ( c ) 一 l ，2 ，) ，或，：v ( c ) u e ( e ) 一 1 ，2 ，) ) 下，对任意相邻或关联的两个元素a ，b g ，有，( o ) ，( 6 ) ，则 称，是g 的一个k 一正常染色 当元素a ，b 均为顶点时，则称，是g 的个k 正常顶点染色 当元素a ，6 均为边时，则称，是g 的一个扣正常边染色 当元素a ，6 是顶点和边时，则称，是g 的一个k 一正常全染色 在上述染色，下，对图g ( u e ) ，定义颜色集合g ( ”) = ，( o ) ia e ( g ) ，a 是与u 关联 的g 中的元素，或 = o ) ，虿( ) = 1 ，2 ，) 一g ( ) 接下来，在上述三种染色的基础之上，附加条件，给出如下所述图的三类染色的定义 5 2 图的三类染色 定义2l 对图g ( v e ) ，f 是如上定义的g 的一个k 一正常染色，若g 中无二色的圈，则 称，是g 的一个k 一无圈染色且称m i n k l g 有k 一无圈染色) 为g 的无圈色数 在定义中： 当，是g 的一个k 正常点染色时，则称，是g 的一个一无圈点染色，简记作k a v c ，且 称( g ) = m 讥 l g 有一无圈点染色) 为g 的无圈色数吼 当，是g 的一个k 一正常边染色时，则称，是g 的一个k 一无圈边染色简记作k a e c ，且 称l ( c ) = m i n k l a 有k 一无圈边染色 为g 的无圈边色数【6 】 猜想矧：对简单图g ，有x ：( g ) + 2 当，是g 的一个一正常全染色时，则也可称，是g 的一个 一无圈全染色 显然，图g 的任一一正常全染色都是g 的一个女一无圈全染色 定义2 2 对图g ( k e ) ，是如上定义的g 的一个k 一正常染色，若对v “u e ( g ) ，确i c ( u ) g ( u ) ，则称，是g 的一个一邻点可区别的染色且称m n i g 有一邻点 可区别的染色1 为g 的邻点可区别色数 在定义中： 当，是g 的一个正常边染色时，则称，是g 的一个k 一邻点可区别的边染色，又称 为k 一邻强边染色，简记作k a v d e c ，h - 称x 。( g ) = m i , 1 k l c 有k 邻点可区别的边染色) 为g 的邻点可区别边色数一个图g 有邻强边染色当且仅当g 没有孤立边 7 1 特别地，当，是g 的一个k 一无圈边染色时，则称这种染色为k - c g 点可区别的无圈边染 色，记作k a a e c ，且称) ( 二( g ) = m 饥 女i g 有邻点可区别无圈边染色) 为g 的邻点可区 别无圈边色数 s 1 显然，对于没有孤立边的简单图，) ( ：。( g ) 存在 当，是g 的一个“正常全染色时，则称，为g 的一个一邻点可区别的全染色，简记 作一a v d t c ，且称x m ( g ) = m i n k l a n k - c g 点可区别的全染色) 为g 的邻点可区别全 色数吼 定义2 3 对图g ( ue ) ，f 是如上定义的g 的一个一正常染色，若对v u ，” y ( g ) ，有c ( u ) e ( ) ，则称，是g 的一个k 一点可区别的染色且称m i n k l c 有k 一点可区 别的染色，为g 的点可区别色数 在定义中： 6 2 图的三类染色 当，是g 的一个k 一正常边染色时，则称，是g 的一个如点可区别的边染色，( 或称k 一强边 染色，或称k o b s - 染色1 口t - a 6 当，是g 的一个k 一正常全染色时，则，称为g 的一个一点可区别的全染色，简记为 k - v d t c 称) ( w ( g ) = m i n k l a 存在k v d t c 为g 的点可区别全色数，记为x m ( g ) 令n d ( g ) 表示g 的破顶点个数，4 p k r ( a ) = m i n l ( d 1 ) n d ( g ) ，5 d ，易得 事实：h t ( g ) k t ( g ) 本文主要对图的三类染色一邻点可区别的无圈边染色，邻点可区别的全染色，点可区别 的全染色分别进行了研究 7 3 邻点n - in 9 0 的无圈边染色 概率方法在研究图的染色方面发挥着极其重要的作用其中邻点可区别的边染 色用概率方法得到了一些很好的结果如a k b a r i ，b i d k h o r i 和n o s r a t i 在文【1 0 】中得到：对任 一无孤立边的图g ，其邻点可区别的边色数) ( ：( g ，1 ) 3 a b m i s t e r ，g y 6 r i ，l e h e l ，s c h e l p 在 文【1 l 】中得到：若图g 没有孤立边，则邻点可区别的边色数x 0 a + o ( 1 0 9 ) ( ( g ) ) h a t a m i 在 文 1 3 1 e 0 得到：若图g 没有孤立边，最大度a 1 0 2 0 ，则邻点可区别的边色数x 乙+ 3 0 0 张忠辅等人在文8 1 中给出了邻点可区别无圈边色数的一个下界：对简单连通 图g ，且iv ( c ) l 3 ，若它的最大度相邻，则 ：。( g ) ( g ) + 1 本节通过应用l o v g s z 局部引理的赋权形式，得到了最大度满足一定限制条件的任意 图g 的邻点可区别无圈边色数的一个上界 定理3 1 对任一最大度为的图g ，a 4 ，有) ( ：。( g ) 茎1 6 a 2 证明 令a d ，c = 1 6 d 2 ，令，：e 一 l ，2 ，g ) 表示g 的边的随机染色，并对任 意e e ( g ) ，( e ) 是从 1 ，2 ，c 1 中随机地均匀地选择的为了保证邻点可区别的无圈 边染色，需满足以下三个条件： f a ) 正常边染色一没有两条相邻的边染成同一种颜色 ( b 1 邻点可区别一没有一对相邻顶点关联同样的颜色集合 ( c ) 任两种颜色所染边的导出子图无圈一没有一个圈的边正常2 _ 染色 为此，定义如下坏事件： ( i ) 对每一对相邻的边e ，令a 。，表示e 和，都被染成相同颜色的事件 ( i i ) 对每一条边8 = u u ，使得d ( u ) = d ( v ) d ( g ) ，令d 。表示所有与u 和 关联的边 的集合，i i p ：d 。= u z e ( c ) ：z y ( g ) ) u v v e ( a ) ：y y ( g ) ) j j a d 。表示所有 与研口 关联的边正常染色，n c ( u ) = g ( ) 的事件 ( i u ) 对每一个2 一圈g ，定义k 类事件a g 为g 的边正常2 一染色的事件 注意到如果( i ) ，( i i ) ，( i i i ) 都不发生，则，是g 的邻点可区别的无圈边染色 r 3 邻点可区别的无圈边染色 ( 1 ) 计算坏事件发生的概率 p r ( a 酊) 2 古，p r ( a 。e ) 2 巧耐可丐 赤，( 2 2 d 一2 ) ，尸r ( a o ) l g 2 2 2 ( 2 ) 计算相关事件数 构造图h ，h 中的结点就是两种类型的所有事件，其中两个结点取和e y ( 每 个x 和y 要么表示一对关联的边，要么表示和一条边关联的所有边及这条边本身的 集合) 相邻当且仅当x 和y 至少含一条公共边因为每个事件e x 的发生仅依赖于x 的 边，所以日就是上述事件的相关图 断言：对每个k 之2 ，没有边存在多于2 一2 个2 k 一圈上 证明 考虑任一边“ ，至多有2 一2 个型如“，z l ，z 2 ，x 2 k - 2 的路从而，至多 有2 一2 个型如u ，。l ，z 引，z 2 k 一2 ，v ，u 的圈 由相关图日的构造，得下表的相关事件数： a 。，a d 。a c a 。， 4 d 一53 d 一22 d 2 1 2 a d ( 2 d 一1 ) ( 2 d 一2 )f 2 d 一2 ) d + l( 2 d 一1 ) d 2 m a c 2 k 2 d ( 2 d 一1 ) 2 k 2 k d 2 一2 注解：对任意k l ，每个k 类事件都包含有2 条边，并且由断言) 对z 2 ，每条边至多属 于d 2 。2 个2 类事件从而由相关图的构造，每一个事件a e , f 与至多4 d 一5 个a e t r 相关，( 因为 和一条边e 相交的边数至多是2 d 一2 ( 除去e 本身) ，事件a 。，中包含两条边e 和，所以分别 和e ，f 相交的边数至多是2 ( 2 d 一2 ) = 4 d 一4 ，又因为和e ( 或，) 相交的边中有，( 或e ) 所 以集合 e ，) 被计算了两次应减去1 ) ，与至多3 d 一2 个a d 。相关，( 令e = u u l ，f = u u 2 ，与 每个点相邻的点至多有d 个，事件a 酊含有三个点，又 u 1 ，u ) ， u 2 ，u ) 各重复计算一次，所 以3 x d 一2 3 d 2 ) ，与至多2 d 2 个a 。相关，( 由断言，每条边至多关联d 2 卜2 个2 f 一圈，f 2 ，事 件a 。f 中包含两条边e ，) 同理可得上表中的其他相关事件数 令p = 击，对每个( i ) 类事件e ，令。= 1 ，对每个( i i ) 类事件e ，令t 2 = 1 ，对每 个( i i i ) q b k 类事件e ，k 2 冷t 3 = 2 ( k 一1 ) ( a ) 若e 是( i ) 类事件，贝 j p r ( e ) = 古= ( 击) “= p t - 9 3 邻点可区别的无圈边染色 若e 是( i i ) 类事件，则p r ( e ) = 南 2 v u t “一1 对( 1 ) ，有： 2 ( 铲2 掣( 3 ) 2 ( 4 d 一5 ) 2 ( 3 d 一2 ) 2 面广+ 而磊面+ 丽孤 南+ 砀茅面+ 南 、羽+ 瓦玎了二可+ 研 因此要证明( 1 ) ，只需要证： 132，】 2 - - d 十百孤i 可十百五产i ， 此式当d 2 时显然成立，从而( 1 ) 式得证 对( 2 ) ，有： 型半+ 毪抖+ ( 2 d _ 1 ) 1 6 4 - - 4 万z - z g _ 1 1 商r 一十丽砑虿玎十p “一叫+ ，8 d 2 1 2 d + 4 4 0 p 一4 d + 2 。2 d 一1 4 d 3 1 0 d 2 + 8 d 一2 、面可厂十1 石孑丁丁二1 丁十百五陌一瓦产瓦f = t 厂 屿群+ l d = 坐瓮箍等必+ 蕊1 0 ) + 南 因此要证明( 2 ) ，只需要证： 着手焉+ 豇1 a o , 删a a 从而( 2 ) 式得证 1 0 3 邻点可区别的无圈边染色 对( 3 ) ，碉： 鬻m + 黜t + 南* 器+ 粼+ 蕊q 2k = 南k + 端+ 石南 ( 南+ 赤+ 南) = 习西圭_ 玎+ 击) k ( 趸南+ 南) 黼2 尚t l o s , 则邻点可区别 的边色数) ( ：( g ，1 ) + 2 7 、五1 ；。瓦虽然研究的只是邻点可区别的边染色，但得到的色数 的界较小，且对本节的研究给予了一定的启发 本节通过尝试对邻点可区别的全染色应用l 0 v 酗a 局部引理的一般形式，得到了邻点可 区别的全色数一个较小的上界 引理4 1 【1 】( b r o o k s 定理) 若g 是简单连通图，g 不是奇圈，也不是完全图，则x ( a ) 引理4 2 1 1 ( v i z i n g 定理) 若g 为简单图，则r ( g ) + 1 定理4 1 如果g ( ve ) 有3 2 21 , 15 ，6 3 2 五i 五，则x “( g ) 2 a + 1 + 2 v - k i f f 五； 进一步，若地( g ) + 2 ，则x m ( g ) a + 2 + 2a , a - i a 证明 由引理4 1 和引理4 2 ，用2 a + 1 种颜色即可以对g 实行正常全染色( 对奇圈和 完全图显然也可以用2 a + 1 种颜色实行正常全染色) ，因此我们有一个2 a + 1 - 全染色，0 然 后，对g 的每条边，每个点独立地，随机均匀地从2 五匠i 五种颜色中以概率击去染色，称 这种全染色为，我们将利用l 0 v 缸z 局部引理证明以正的概率，是邻点可区别的全染色 为此，定义如下坏事件： ( i ) 对每一对相邻的边a = e ，e 2 ) ，令玩表示e ，和e z 被染成同种颜色的事件 ( i i ) 对每一条边b = “ e ( g ) ) ，令e 8 表示痢 被染成同种颜色的事件 ( i i i ) 对每- - 4 k i 2 g ( 。，。) = e = “ e ( g ) ) ，令e c 。表示e 和某一端点被染成同种颜 色的事件 ( i v ) 对每一条边e = ，使得d ( u ) = d ( v ) j ( g ) ，令d 。表示u 和 ，以及所有与u 和”关 联的边的集合，即：d 。= u ) u u e ( g ) ：z y ( g ) ) u ”可e ( c ) ：y y ( g ) ) 则点h 表示泖 ，以及所有与卿 关联的边正常染色，r c ( u ) = c ( ”) 的事件 】2 54 邻点可区别的全染色 ( 1 ) 计算坏事件发生的概率 p r ( 毋) = ( 2 甲) ( 砸1 ) 2 = 彘、訾，p k e e ) = 彘 警? p r ( 魄h 。，) = 2 ( 2 以p ) ( 击) 2 = 志 警 令e = 删，d ( u ) = d ( v ) = d , 若e d 。发生，l j d 。中的点和边均i f _ 常染色r o ( u ) = g ( ) ，令g ( 珏) 一 ，( e ) ) = g ( ) 一 ，( e ) = g 假设c 是固定集合且有 种新颜色，有d 一 种 旧颜色，这种事件发生的概率为： 呻一 訾) “( 击) 】2 脚印( 一、警( d 一 ) ) ( 击) 】2 ( 击) 2 t e x p ( 一 傈( d i ) ) 脚(ed旌2笺囝(2绎)(击2iexp(ed ) ：i e x p ( 一 屠( ) ) 脚 。) 堇囝( 2 气h 6 ) ( 曩医一 、号 ( d 一 ) ) 2譬(和卫尘譬巫)t(击)zte印(一譬()i 2 瓜= 0 ( 一2 + 寻擎1 6 z a 此z 瓜) t 。印( 一 傈回 s 。印( 一 傈d ) 2 瓜( 。+ 寻1 6 2 坐舟t 由于3 2 、五瓦函，所以、马兮壶，因此有： 2 室c 学偿腿2 室c 学扮 曼( 去) t = 曼( 击) 播 ( 注：击e 2 + 南 1 时显然成立，从而( 2 ) 成立 对( 3 ) ，有： ( 1 一丽4v 尢- - 以a - ”j ( i - 志 警) 2 ( 1 一彘 警) ”i - 去) 丛 ( ) 击舟击佴+ 去：( ) 舟去 ( ) 彘+ 去= 矿i 珏i 因此要证明( 3 ) ，只需要证： s ( 2 ij - 日i + 击，上式当 1 时显然成立，从而( 3 ) 成立 对( 4 ) ，有： 去( - 一志晒4 d ( 1 - 志雁) 2 ( 一志 譬) 蛆( i - 去) 蝉 e x p ( 一m ( s a 2 ) ) e 印( 一 警d ) e x p ( 一击 警) e 印( 一 警) - e 印( 一j ) = e z p ( - 2 m a - 、訾d 一品 訾一i n 8 0 5 ) 因此要证明( 4 ) ，只需要证： i e 印( 一 警d ) 冬e 印( 一2 1 n 一 訾d 一盎 警一1 , 1 8 一o 5 ) 一 雁d + l n i 一2 m a 一 停d 一丧傈一h i 8 - 0 5 即证： 鬯今d 一南 号兮一2 1 n 一i n l 2 一o 5 2o 又； 号兮d 一岳 号兮一2 1 h a i n l 2 一o 5 2 1 h a 一南 警岫1 2 “5 2 1 n 一盎刍一l n l 2 0 5 只要证：2 1 h a 一矗击一l n l 2 0 5 0 而上式当5 时显然成立，从而( 4 ) 成立 综上，由引理1 4 知，g 存在2 a + i + 2 五i 五一邻点可区别的全染色 定理4 1 的后半部分由上述证明知显然成立，从而定理得证 5 点可区别的全染色 1 9 5 5 年，m y c i e l s k i 1 1 构造了一种最简单的图( 称为m y c i e l s k i 图) 证明了：存在任意 大( 点) 色数的无三角形图之后，m y c i e l s k i 图引起了许多学者浓厚的研究兴趣，得到了 一系列好的成果如文f 1 6 1 中对于路、圈、完全图、完全二部图、星、扇、轮等特殊图 类，得到了其m y c i e l s k i 图的邻点可区别全色数但点可区别的全染色，比邻点可区别的全 染色研究难度大，现在得到的结果较少下面两小节我们尝试研究特殊图的点可区别的全 染色，在理论上有了一定的改进和推广 5 1 关于几类特殊图的m y c i e l s k i 图的点可区别的全染色 本小节首先给m y c i e l s k i l n 的定义，然后通过具体构造染色的方法，讨论并给出了 路、圈、完全图、星、扇、轮的m y c i e l s k i t 5 l 的点可区别全色数 定义5 1 1 s 】对图g ( ue ) ，m ( g ) 称为g 的m y c i e l s k i 图， y ( m ( g ) ) = v ( a ) uv u ) ； e ( t ( g ) ) = s ( a ) u u ”iu y ( g ) ，u 7 v7 ，u v e ( g ) ) u w v 7i 7 v ) ；其 中，v = u i y ( g ) ) ， ) n ( v ( g ) u v ) = 曲 i 5 ，n = 2 ，3 ； 定理5 1n p n n n n ，则) ( “( m ( r ) ) = 6 ，n = 4 ； 【n + 1 ，礼25 证明 设p 忆= l 0 2 7 ) 3 v n 考虑以下4 种情形： 情形1 ： = 2 此时m ( p 2 ) = g ，是5 个点的圈，k r ( m ( p 2 ) ) = 5 ，n n x 。( m ( b ) ) 5 易 找到m ( p 2 ) 的一个5 v d t c 法详证略去 情形2 ：n = 3 b ( m ( p 3 ) ) = 5 闺此x “( m ( p 3 ) ) 5 t i 正x 。( m ( b ) ) 5 ，为此，仅需证 咀m ( p 3 ) 存在一个5 - v d t c 即可如下定义一个从y ( m ( b ) ) ue ( 州( b ) ) 到 1 ，2 ，3 ，4 ，5 的 映射，： f ( v - 0 2 ) = f ( v 2 ) = f ( ”i w ) = 1 ；f ( v 。”：) = f ( v 。v 。) = ，( ”i ) = ，( 运”) = 2 ；f ( v 3 ) = ，她u i ) = f ( v a ) = f ( v 2 w ) = 3 ；f ( v 2 v a ) = f ( v 1 ) = f 0 ) = 4 ；f ( v 2 ) = ，( 吨”：) = 5 易验 证，是m ( p 3 ) 的一个5 - v d t