（应用数学专业论文）图的若干特殊正常全染色.pdf

摘要 本文对邻点可区别全染色、d ( 国一点可区别全染色和伊不足全染色等几类特殊的正 常全染色进行了探讨 第一部分给出最大度为5 的2 连通外平面图的邻点可区别全色数的具体值；第二部 分对詹= 3 ，4 ，与2 为奇数) 的循环图g ( 1 ，k ) 作了具体地邻点可区别全染色；第三部分 利用组合数学中的h a l l 定理得到树的d ( 2 ) 一点可区别全色数；第四部分提出一个新定 义图的肛不足全染色，并应用概率论中的l a v d s z 局部引理的一般形式得到最大度至 少为5 的图的伊不足全色数的一个上界 关键词：全染色；邻点可区别全染色；d ( 卢) 一点可区别全染色；伊不足全染色；外平面 图；循环图；树 a b s t r a c t i nt h i sp a p e r ，w ed i s c u s ss e v e r a ls p e c i a lp r o p e rt o t a lc o l o r i n g so f g r a p h s ，i n c l u d i n ga 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 g ，d ( f 1 ) 一 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 卢- f r n g a lt o t a lc o l o r i n g i ns e c t i o no n e ，t h ee x a c tn u m b e r s 、o f2 - c o n n e c t e do u t e r p l a n a rg r a p h 8 w i t hm a x i m u md e g r e e5a r eg i v e n ；i ns e c t i o nt w o ，c i r c u l a rg r a p h s c k ( 1 ，k ) a r ee x a c t l yv e r t e x - d i s t i n g u i s h i n g l yt o t a l l yc o l o r e dw h e nke q u a l s t ot h r e e ，f o u r ，堡( ni so d d ) ，r e s p e c t i v e l y i ns e c t i o nt h r e e ，ad ( 2 ) 一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 ft r e e si so b t a i n e db yv i r t u eo f h a l l ，st h e o r e mi nc o m b i n a t o r i a lm a t h e m a t i c s i ns e c t i o nf o u r ，an e wd e f t n i t i o n ，a 卢一t r u g a lt o t a lc o l o r i n go fg r a p h s ，i sp r o p o s e da n dt h eg e n e r a lf 西m o fl o v d s zl o c a ll e m m ai np r o b a b i l i s t i ct h e o r yi su s e dt og e to n eu p p e r b o u n do ft h ef l - f f u g a lt o t a lc h r o m a t i cn u m b e ro fg r a p h sw i t hm a x i m u m d e g r e ea ti e a s t5 k e y w o r d s ：t o t a lc 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 gt o t a lc o l o r - i n g ；d ( f 1 ) - 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 ；f l - f r u g a lt o t a lc o l o r i n g ；o u t e r p l a n a rg r a p h ；c i r c u l a rg r a p h ；t r e e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包含为获得西北师范大学或其他教育机构的学位或证书而使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示了谢意。 群：鹕老 日期：爰叻i 年s 月上日 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、 交论文的复印件，允许论文被查阅和借阅： 采用影印、缩印或其他复制手段保存论文。 使用学位论文的规定，即：学校有权保留送 学校可以公布论文的全部或部分内容，可以 ( 保密的论文在解密后应遵守此规定) 签名：豕易骞导师签名：做，凇日期：o ) 幻( 年s 月硝日 刖茜 众所周知，图的染色问题一直是图论学科的一个重要研究领域，目前，图的染色主 要包括点染色、边染色、面染色以及点边、点面、边面和点边面全染色这些年来，许 多数学研究工作者一方面致力于对已有问题地深入探讨，另一方面又在不断提出新的课 题继b u r r i s 和s c h e l p 【1 】，b a z g a n 2 及b a l i s t e r l 3 探讨了图的点可区别正常边染色之后， 2 0 0 2 年张忠辅等【4 】又提出了图的邻点可区别边染色( 也称邻强边染色) ，现已取得许多有 价值的成果紧接着，在2 0 0 4 年，张忠辅、陈祥恩等i s , 6 又提出图的邻点可区别全染色，并 对圈、完全图、完全二部图、扇、轮、树和奇数阶完全图删去条边所得到的图的邻 点可区别全染色进行了讨论，确定了这些图的邻点可区别的全色数根据这些结果，他 们还提出一个猜想( 对于阶数不小于2 的简单连通图g ，x 。( g ) a ( c ) + 3 ) 和一个公开问 题( 如果日是g 的一个子图，那么在什么情况下有x “( 日) ) ( m ( g ) 呢? ) 文献【7 】给出了 路、圈、完全图、完全二部图、星、扇和轮的m y d e l s k i 图的邻点可区别的全色数文 献【8 】给出了奇数阶完全图删去一条长为3 的路所得到的图，即玛。+ 1 一e ( r ) 的邻点可区 别全色数关于邻点可区别全染色的其余文章请参阅文献睁1 2 】本文的第一部分给出了 最大度为5 的2 _ 连通外平面图的邻点可区别全色数由于循环图具有优美的对称性和潜在 的实用价值，人们对其作了诸多研究| 1 8 - 1 7 1 ，而且还大量应用于多计算机系统网络及分布 式计算 i s , i q 本文第二部分讨论的是几类4 - 正则循环图的邻点可区别全染色 张忠辆【2 0 】和a k b a r i 2 1 】各自独立地给出了与距离有关的一种特殊边染色，并就这类 染色对一些图作了研究，得到了相应的边色数之后，张忠辅等在文献 2 2 l 又提出d ( 卢) 一点 可区别全染色，并对路、圈、完全图、完全二部图、路与路的联图和路与圈的联图作 t d ( 2 ) 一点可区别全染色在此基础上，本文第三部分继续探讨树的d ( 2 ) 一点可区别全染色 目前，概率方法在图的染色方面发挥着日益重要的作用，借助它我们可以得到阶数 较大的一般图的若干色数的上界仁3 。目，其中l o v a s z 局部引理就是一个非常重要而有力 的工具上世纪9 0 年代，h i n d ，m o u o y 和r e e d 在文献 2 6 1 提出了图的伊不足点染色的概 念，并在文献【2 5 】和1 2 6 】中分别用l o v d s z 局部引理的不同形式给出其色数的上界，还指出 由l o v d s z 局部引理的一般形式得到的结论是最好的本文第四部分首先给出图的肛不 足全染色的新定义，然后也应用l o v d s z 局部引理的般形式得到良不足全色数的一个 上界 文中涉及的术语遵从文献2 6 ，2 7 ，2 8 1( g ) = 5 的2 一连通外平面图的邻点可区别全染色 1 相关知识 定义i i 2 s l 设g e ) 是阶数至少为2 的连通图，k 是正整数，映射，：v ( c ) u e ( c ) 一 l ，2 ，七 若 1 ) 对任意的，v w e ( g ) ，u 有，( u ) ，( t 脚) ； 2 ) 对任意的伽e ( g ) ，u ”，有， ) ，( ”) ，( u ) f ( u v ) ，f ( v ) f ( u v ) ，则称， 是g 的k 正常全染色 定义1 21 5 ，q 设g ( y ，e ) 是阶数不小于2 的连通图，膏是正整数，映射，：v ( a ) u e ( c ) 一 1 ，2 ，) 对任意的u y ( g ) ，i a c ( u ) = ，( u ) ) u f ( u v ) u v e ( g ) ， y ( g ) ) 和百( u ) = 1 ，2 ， 一g ( t ) 如果 1 ) 对任意的， e ( g ) ，u ，有，0 ) ， d ) ； 2 ) 对任意的“u e ( g ) ，u ”，有，( u ) ，( ”) ，m ) ，( u ”) ，f ( v ) ，( 伽) ； 3 ) 对任意的u ”e ( g ) ，有g ( ) g 扣) ； 那么称，为g 的缸邻点可区别全染色，简记为k - a v d t c 称g m ) 为顶点u 的色集合称数 脚( g ) = l i n 仕i g 存在七一a v d t c 为图g 的邻点可区别全色数 由定义可知，下面的引理是显然的 引理1 11 5 , 6 1 当g 中不含相邻的最大度顶点时，t ( g ) a ( g ) + 1 ；当g 中含有两个 相邻的最大度顶点时，x m ( g ) a ( c ) + 2 作者将分两部分内容分别探讨最大度为5 的2 连通外平面图和几类垂正则循环图的邻 点可区别全染色 定义1 31 2 7 】设连通图g 不是完全图，v l 是v ( g ) 的一个非空真子集，若g 一非连通， 则称是g 的顶点割 定义1 4f 2 7 l 图g 是n 阶连通图，令 邵) ： 慨 i v l l m 鄹的顶点割l 韶帏在两个不相邻的顶茂 in 1 ，若g 以为生成子图 称形( g ) 为g 的连通度 2 1 ( g ) = 5 的二连通外平面图的邻点可区别全染色 定义1 5 【2 7 l 称图g 是b 连通的，若0 k ( g ) 定义1 6 矧若平面图g 的所有顶点都在某个面 的边界上，则称g 为外平面图 ，o 为g 的外部面 由于有割点的外平面图可断裂为若干无割点的外平面图分别进行研究，所以我们总 假设图g 是一个2 _ 连通外平面图 引理1 21 1 2 设图g 是( g ) 4 的2 _ 连通外平面图，则以下五条至少有条成立： 1 ) 府在u ， y ( g ) ，使得如= 奶( ) = 2 ，伽e ( g ) i 2 ) 存在“， ，t ，u l ，口l y ( g ) ，使得如( ) = 如( 口) = 2 ，如) = 4d a ( u 1 ) 4 ，d a ( v 1 ) 24 ，t l ，u 叫，v 0 1 ，v w ，让1 t i tv l l l ) ，珏1 l e ( g ) ； 3 ) 存在u ， a i ，u ，饥， 0 2 ，枷， l y ( g ) ，使得d a ( u ) = d g ( u ) = d g ( ) = 2 ，d a ( v 1 ) = 如( 啦) = 4 ，d a ( 钍1 ) 4 ，d a ( 叫1 ) 4 ，t u l ， l ， u l u 1 ，v 0 1 ，口t j 2 ，钉1 t j 2 ，忱叫，吨甜1 ，w w l ，钍1 叫l e ( g ) ； 4 ) 存在u ，“l ， ， 2 ， ，w l y ( g ) ，使得d a ( u ) = 如( u ) = d g ) = 2 ，d a ( v 1 ) = 如( 也) = d c ( t ，1 ) = 4 ，d a m l ) 24 ，钍 1 ，u 口l ，u 1 钉1 ，t 脚1 t v v 2 ，u 1 抛，t j 2 t ，刨2 铷l ，伽叫l e ( g ) ， u l 如1 毛g ( g ) ； 5 ) 存在牡，口，伽y ( g ) ，使得伽， a t l ) ，讹，e ( g ) ，d a ( u ) = 2 ，d g ( 口) = 3 ，3 d g 似) 茎 ( g ) 2 主要定理 用么( ( g ) l 表示图g 中全体最大度顶点构成的集合 定理1 1 设g 是( g ) = 5 的2 一连通外平面图，若e ( g 【坛( g ) 1 ) = 曲，则 x “( g ) = 6 证明 对i v ( g ) l 进行归纳 若l v ( g ) l - 6 ，则g 是一个扇且易得x ( r ) = 6 假设结论对满足( 日) = 5 ，e ( 日【坛( 日) j ) = c r i v ( h ) l 6 ) 的2 - 连通外平面 图日成立现考虑满足( g ) = 5 ，e ( g 【垤( g ) 1 ) = c r w ( g ) i = p 的冬连通外平面图g 由 引理1 2 ，分以下四种情形( 其中情形3 是将引理1 2 中的情形3 和4 合并而得到的】： 3 1 ( g ) = 5 的2 一连通外平面图的邻点可区别全染色 设g 中任意两个度为2 的顶点均不相邻，且g 是6 种颜色的集合 情形1 存在，口y ( g ) ，使得d a ( u ) = d a ( v ) = 2 ，饥，e ( g ) 设u oe ( ) 一 口 ，t j 0 舀( 一 牡) i 殳d g ( u o ) 2 ( 否则，u ，u o 与u ，w 的情形相同) 令日= g t + u o v ，则日是( 日) = 5 且i y ( 日) i = p l 的2 连通外平面图由归纳假设，日有一 个6 一a v d t ch 令9 ( 伽o ) = h ( u o v ) 若d a ( o ) 2 或 ( ) 百( ) ，则设g ( u v ) g 一臼( 伽) ，h ( v o 口) ， ( ) ) ；若如( 啦) = 2 且 ( ) c k ( 咖) ，则设g ( u v ) c 一妇( 伽o ) ) 一c k ( ) 设9 ( u ) c 一 扣) ，h ( u o ) ，9 ( u 咖) ，9 ( 咖) ，对于任意z v ( a ) ue ( a ) 一u ，u u o ，u ) ， 设9 ( z ) = ( z ) ，显然g 是g 的6 - a v d t c 情形2 存在u ， ， ，u l ，。l y ( g ) ，使得d a ( u ) = d g ( 口) = 2 ，d a ( w ) = d r ( v 1 ) = 4 ，4s 商岔( 牡1 ) s5 ，m n ，砒u ，u l 删， 叫， 0 7 1 1 ， l 叫，u l 1 e ( g ) 令h = g u ，贝日是l 矿( 日) i = p 一1 的2 - 连通外平面图由归纳假设，日有一个6 - a v d t ch 情形2 1 d c ( 缸1 ) = 4 ，设u 2 j v 舀( “1 ) 一 让，1 1 1 ， 1 ) 情形2 1 1 d a ( 撕) = 4 1 ) 砩( u 2 ) = g ( 1 ) 设z = 刁h 他) = - h 如1 ) 若z g ( 让。) ，则设g ( u u l ) g 一铱 1 ) ；若雁矾心- ) ，则设 g ( u u l ) = 2 设z t 铱m ) 一( 晚( 牡1 ) u g ( “u 1 ) ) ) t ) 若z ，z 7 g i ( t i ，) ，则设g ( u w ) c c ( ) 一 9 ( w ) ) ； 瓿) 若 c k ( 叫) ，z 目孔( ) ，见l # g ( u w ) = j 7 ； i i i ) 若堤c k ( u ) ，z 7 g 知) ，g ( u u l ) = ? ，则设h ( 1 ”) = c ，并交换讹1 和u l 叫的颜色设 9 ( u w ) 0 ，c ，h ( 叫) ，h ( v l 叫，h ( ) ) ； i ) 若f ，f 写q ) ，则令g ( u w ) = ， 并重新定义口( 删) = z ，9 p ) c 一 ( 删，) ，9 扣) ， ( t u ) ， ( 钉) ) 设9 ( u ) 为g 中除删l ，钍t ，钍。，埘的颜色外的任何一种颜色对于所有的z v ( g ) u e ( g ) ， 若z 在9 下未被特别染色，则令9 ( 。) = 危( 。) ，显然9 是g 的6 - a y d t e 2 ) q 池) 晚h ) 设c 1 g ( 1 ) 一q ) ，白g ( n 2 ) 一瓯( 口1 ) 若c l ，c 2 a ( u 1 ) ，则设9 ( 伽1 ) g g 心1 ) ；若c 1 e c h ( u 1 ) ，饧瓯m 1 ) ，则令9 ( u u l ) = c l ；若c 1 c h ( u 1 ) ，乐瓯1 ) ，则令g ( 伽1 ) = 0 2 ；若c 1 ，c 2 毛瓯( 1 ) ，则令9 ( 1 ) = c 1 ，并重新定义九( 钍l t o ) 为9 m l ) = c 2 ， ( 叫) 为9 ( ) g 一 晚，h ( u ) ， ( 1 ) ， ( 让1 ) ，h ( w v l ) ，h ( w v ) 为9 ( w v ) c 一 c 2 ， ( ) ， ( 口) ，h ( w v l ) ，危( 口1 ) ) 4 1 ( g ) = 5 的2 - 连通外平面图的邻点可区别全染色 令( t u ) = 9 ( 删u 1 ) ，危( t u u l ) ，9 ( 。) ，g ( t u ) ) ，c ；( “1 ) = ( 乱1 ) ， ( 让1 t 2 ) ，g ( 钍1 ) ， ( u l 1 ) ， g ( t u 1 ) ) 设2 q ( 1 ) 一g ( u 1 ) i ) 若f ) ，则令9 ( 僦u ) g 一) 一臼( 伽1 ) ) ； 托) 若雁) ，则令9 ( u w ) = f f 设u 染e 中除牡t l ，w ，u 1 ，衄之外的任何一种颜色对于任意z v ( c ) u e ( a ) ，若在9 下 未被特别染色，则令9 ( z ) = h ( z ) ，显然9 是g 的6 - a v d t o 情形2 1 2 d g ( u 2 ) 4 当g ( u 1 ) 垡q ( 口1 ) 时，设g ( u u l ) o - - g ( 1 ) ；当g ( t 1 ) 瓯( 口1 ) 时，设9 ( 她1 ) e 一 矗( ) 令g ( t 1 ) = g ( u 1 ) u 9 ( 1 ) ) ，显然g ( u - ) 岛( 1 ) ，设c 1 g ( u 1 ) 一g ( u 1 ) ，c 2 c k ( 1 ) 一c ；( u 1 ) ，( 矗( ) = 危( u l ) ，h ( v l , o ) ，_ l ( t ，) ， ( ) ) 1 ) 若c l ，c 2 c k ( w ) ，则设9 ( u w ) g c k ( ) 一 9 ( u u l ) ； 2 ) 若c 1 c k ( ) ，c 2 毛c k ( ) ，则设9 ( u w ) = c 2 ； 3 ) 若c l g 瓯( w ) ，c 2 g ) ，g ( u u l ) c l ，则设9 ( u w ) = c l ； 4 ) 若c 1 毛瓯) ，c 2 魄) ，g ( u u l ) = c 1 ，则交换1 和 u 1 的颜色，并设g ( u w ) g 一 ( 叫) ， ( 叫 ) ，h ( 埘钉1 ) ，g ( 札t 1 ) ，g ( 钍1 ) ) ； 5 ) 若c l ，c 2 毛瓯) ，则设9 ( u w ) = 晚，重新定义h ( w v ) 为9 ( w v ) = c 1 ，7 l 一) 为9 ( w ) g 一 c ， ( t u ) ， 0 1 ) ， ( 口 1 ) 设9 ( u ) g 一伽( 鲫) ，h ( u 1 ) ，g ( u ”1 ) ，g 托 ) ) 对于任意。v ( a ) u e ( g ) ，若在9 下未被 特别染色，则令g ( z ) = ( z ) ，显然g 是g 的6 - a v d t o 情形2 2 d g ( 让1 ) = 5 ，乱2 ，蛳n g ( t 1 ) 一 u ，叫，可1 ) 且d g ( u 2 ) 5 ，如( 吣) 5 设9 ( u u l ) g 一倪( “1 ) 若q ( t ，) 巴) ，则重新定义h ( w v ) 为9 ( 叫”) = d g 池) ，并令9 ( 删) = g 一 g ( u u l ) ，g ( v w ) ，h ( 1 叫) ，危( u 1 ) ， ( w ) ) 若眦，又与 同色，则改 ( ) 为9 ( ) g 一 九( 1 ) ， ) ，危( ”，) ，g ( 砌) ) 若繇( ”) 譬c k ( ”，) ，则设g ( t 。”) = c ( 矗( 叫) 一 9 ( 钍u - ) ) 设9 ( u ) c 一 h 扣1 ) ， ) ，g ( 伽1 ) ，9 ( j ) ) 对于任意z v ( c ) u e ( a ) 一 t ，钍u l ，让 ) ， 设9 ( z ) = ( z ) ，显然9 是g 的6 - a v d t c 情形3 存在u ，u l ，口，口1 ，啦， ，l y ( g ) ，使得如m ) 一如( ) = 如) = 2 ，如m ) = d a ( v 2 ) = d 0 ( 1 ) = 4 ，4 d g ( 让1 ) 5 ，t 1 ，t 上 l 钍l 口l ，t ， l ，w 啦，t 吃”l 2 t l ，抛t ，l ，叫t 也e ( g ) 令日= g 一口，则日是l v ( 日) i = p 一1 的2 - 连通外平面图由归纳假设，日有一个6 - a v d t gh 5 1l x ( g ) = 5 的2 连通外平面图的邻点可区别全染色 情形3 1 如( “1 ) = 4 当瓯( 1 ) 瓯( u - ) 时，设9 ( v v l ) g q ( “1 ) ；当q ( t ，) 垡g ( u 1 ) 时，设9 ( v v l ) g q 扣) 令g ( u ) = g ( 口，) u 妇( 删) ) 若岛( 口，) = 魄( t f j ) ，则当瓯池) 晚( 叫1 ) 时，设g ( v v 2 ) g g ( ”) ；当g 他) 垡 g ，) 时，设g ( w 2 ) g 一嘛池) 一幻扣”1 ) ) 若q ( v 1 ) 晚( 叫，) ，设c t 魄( ，) 一g ( 口- ) ， c 2 g ( 1 ) 一岛( 1 ) 以下讨论过程完全类似于情形2 1 的2 ) ，从而可得到g 的一个6 - a v d t c 情形3 2 d g ( u 1 ) = 5 若瓯池) 以( 1 ) ，则- 设g ( v v 2 ) g g ( 锄1 ) i 若瓯她) 垡g ( - ) ，则设9 ( m t ) g 一瓯池) 令g ) = 瓯她) u g ( 口睨) ) 若晚( 1 ) g 她) ，则设9 ( 口m ) g q 他) ； 若魄( u ) 垡g ( 址) ，则设g ( v v l ) g 一瓯0 , 1 ) 一妇( 啦) 设g ( ”) g 一 ( ，) ，h ( t j 2 ) ，9 ( 口1 ) ，9 ( 啦) ) 对于任意z v ( a ) u e ( g ) 一扣， 3 0 1 ，v v 2 ， 设g ( z ) = ( z ) ，显然9 是g 的6 - a v d t c 情形4 存在u ， ，叫y ( g ) ，使得d a ( u ) = 2 ，d g ( ) = 3 ，3 d g ) 5 ， ， u 曰( g ) 设 l 0 ( ) 一 让，伽 令h = g t ，则日是l y ( 日) = p l 的2 - i g n _ # l - 平面图 由归纳假设，贿一个6 - a v d t ch 情形4 1 d g ( ) = 3 ，设 u j l t g ( t ，) 一 t ， ) 情形4 1 1 始( 1 ) 3 ，d a ( v 1 ) 3 设9 ( w 由g 一 h ( ”- ) ， ”) ， ) ) ，岛) = 取) ud u ) 当瓯( o ) g ( t l j ) 时，设9 ( u v ) c q ) ；当仉( 口) 垡q ( ) 时，设g ( 删) c 一 ( 口) ， ) ，h ( v v l ) ，g ( t i u ) ) 话l 9 ( u ) g 一 危( 口) ， ( 叫) ，9 ( 叫u ) ，g ( 删) 对于任j 蘸z y ( g ) ue ( g ) 一 ， u ，“ ， 设g ( z ) = ( z ) ，显然9 是g 的6 - a v d t o 情形4 1 2 d g ( 1 ) = 3 ，d o ( 1 ) 3 若铱) 婊( 训，) ，则设9 u ) e 一瓯( 1 ) ；若q ) g 瓯1 ) ，则设g ( u ) g 一魄) 令q ) = q ) u g u ) ) 若g ( 口) q ) ，则设9 ( u v ) g g ( ”) ； 若岛( ) 垡q ( ) ，则设g ( u ”) g g ( ”) 一 9 ( ) ) n ：g ( u ) g 一 h ( t l ，) ， ( ) ，9 t ) ，9 ( w ) ) 其余边与点的染法同上 情形4 1 3 d 0 ( 口1 ) 3 ，d g 扣1 ) = 3 此时，讨论与情形4 1 2 相同 情形4 1 4 如( u 1 ) = d g ( u - ) = 3 6 1a ( g ) = 5 的銎连通外平面图的邻点可区别全染色 1 ) 若c k ) 垡c k 1 ) ，c k ( 口) 垡瓯( 1 ) ，则讨论与情形4 1 1 相同 2 ) 若吼) 鐾晚( 叫1 ) ，g ( 口) 瓯) ，则设g ( u v ) c c h ( 1 ) 令g ( 口) = c h ( 口) u g ( 一) 当瓯( 衄) 垡q ( ”) 时，设9 ( 删) c g ( w ) 一扫( “”) ，；当q ( 埘) g ( u ) 时， 设g ( u w ) c g ( t ，) 除删，u 外，汲其它边和点的染法同情形4 1 2 3 ) 若c k ( ) c h 扣1 ) ，c k ( 口) gg ( 1 ) ，则与2 ) 有相同的讨论 4 ) - 若瓯( 叫) 瓯( 叫- ) ，g ( ”) g ( ) ，则设g ( u w ) a 一繇( ，) ，g ( 钿) = 巴( 伽) u g ( t m ) ) 若g ( 伽) = g ( 1 ) ，则设g ( u v ) g c h ( v 1 ) 若g ( ) 倪( ，) ，设c - g ( 加) 一魏( 口1 ) ，c 2 e h ( v 1 ) 一岛( ) 若c l a ( ，c 2 毛 瓯( ) ，则设g ( u v ) = 龟；若c l 毛e h ( v ) ，c 2 g ( u ) 且9 ( w ，) = c 1 ，则令g ( 伽) = 饧，并交换“ 与删口的颜色；若c 1 ，c 2 - c h ( v ) ，则有以下三种情形： i ) 若 ( ) c 1 ，则令g ( v ) = c 1 ，g ( u v ) = 0 2 ； 托) 若五( ) = c 1 ，9 ( 饥) c 2 ，则令9 扣) = c 2 ，g ( u v ) = c l ； i i i ) 若 ) = c 1 , g ( v 1 ) = c 2 ，假设g ( u w ) = c 3 ，则c 3 瓦1 ) ，交换“ 与的颜色，并 重新定义 ( ) 为9 ) = c - ，同时设g ( u v ) = c 2 9 ( 曲是g 中不是t 舢，伽， t o ， 所染的任何一种颜色对于任意z v ( g ) ue ( g ) ，若 在g 下未被特别染色，则令g ( z ) = ( z ) ，显然g 是g 的6 - a v d t c 情形4 2 d g ( ) = 4 ，设w 1 ，w 2 b ) 一扣，口) 情形4 2 1 d o ( w 1 ) 4 ，d a ( w 2 ) 4 ，设 1 屺p ) 一 u ，训 设g ( u w ) = c g g ) 若繇( 口) 垡瓯h ) 或如( ”) 如( 1 ) ，则设g ( u v ) g 一瓯( ”) 一料；若铱( ) g ( 口) ， d o ( v ) = 如( 1 ) 且c 瓯( 1 ) ，则设g ( u v ) c g ( 口1 ) ；若g ) 晚( 口1 ) ，如( ) = d g ( 仇) ， 但i 百铱0 1 ) ，则重新定义 ( ) 为g 扣) = c ，设g ( u v ) c 一 h ( v v l ) ，h ) ，9 扣) ，9 ( 删j ) 设g ( 钍) g 一 危) ， ( 口) ，9 ( 删，) ，g ( “口) ) 对于任意z v ( g ) u e ( g ) ，若在9 下未被特 别染色，则令9z ) = ( = ) ，显然g 是g 的6 - a y d 粥 情形4 2 2 1 ，地在g 中的度恰有一个等于4 不失一般性，可设d g ( ”1 ) = 4 ，如( 叻) 4 当q ( t l ，) 倪( t c ，- ) 时，设9 ( 埘) g g ( t 1 ) ；当瓯( ) 垡瓯( 1 ) 时，设9 ( 删) c 一瓯( 叫) 若铱如) q ( - ) 且d a ( v ) = d g ( 口，) ，则设9 ( “口) a 一瓯( 1 ) 一 g ( u 删) ) ； 若g ( ”) g 瓯h ) 或d g ( ”) d g ( - ) ，则设9 ( 一) c q ( ”) 一0 ( u ”) ) 7 1a ( c ) = 5 的2 一连通外平面图的邻点可区别全染色 设9 ( u ) c 一 ) ，危( ) ，9 ( 伽u ) ，9 ( 伽) 对于任意zev ( c ) ue ( g ) ，若在g 下未被特 别染色，则令g ( z ) = ( z ) ，显然g 是g 的6 一a v d t c 情形4 2 3 d c ( i ) = d e ( 2 ) = 4 若q - ) = 瓯她) ，则当瓯) 垡魄扣) 时设g ( u w ) c g h 扣) ；当繇恤) ( k ( 1 ) 时，设g ( u w ) c c k ( 伽1 ) 若o ( 1 ) g ( 地) ，设c 1 g ( w 1 ) 一c h ( 2 ) ，c 2 g ( 她) 一g ( 啦) ，则c 1 g ) 和 c 2 g ( t ，) 中至少有一个成立 1 ) 若c l ，c 2 瓯( ) ，则令9 ( u w ) c g ( ) 2 ) 若c 1 c k ( ) ，c 2 ；( 矗( ) ， i ) 若 l 或v w ( u w ) 染了c l ，则改u w ( v w ) 的颜色为睨； i i ) 若h ( w ) = c l ，则令g ( u w ) = c 2 3 ) 若c 1 - g c h ( t f j ) ，c 2 瓯( t ，) ， i ) w w 2 或u ( 伽) 染了c 2 ，则改w ，( ) 的颜色为c l ； 母若h ( ) = c 2 ，则令9 ( w ，) = c ( ) = 7 l ( 口1 ) ， ( ”) ，g ( ) ) 若( ) q ( 口1 ) 且d g ( ”) = 如( 口1 ) ，则设9 ( 伽) d c k ( ”1 ) 一 g ( t t l j ) ) ；若l 爿 ) 垡g i ( 1 ) 或d g 0 ) d e ( 1 ) ，则设g ( u v ) c 一( y ) 一 9 ( ) ) 设9 ( u ) 为异于 ， ，删，w 的g 中任一种颜色对于任意z y ( g ) oe ( c ) 一 u ， ，u ) ，设g ( z ) = h ( z ) ，显然g 是g 的6 - a v d t c 情t v 4 3 d a ) = 5 ，设w l ，毗，嘶 b ( ) 一 u ，口) 且d g 1 ) ，d g ( 她) ，d g ( 讹) 均不等 于5 设g ) c g h 似) 若g 0 ) c a ) 且d g 0 ) = d o ( v ) ，则设9 泓，) g g h ( 口1 ) _ d ( 让似) ；若瓯( ”) 鐾q ( ”1 ) 或d a ( v ) 如扣- ) ，则设g ( u ”) e c d v ) 一 9 ( 让t l j ) 设9 ) c 一 _ l l ( 口) ， ) ，g ( w ) ，9 ( m u ) ) 对于任意z v ( c ) u 目( g ) 一 札，t ，t ) ， 设9 ( z ) = ( z ) ，显然g 是g 的6 - a v d t c 定理得证 定理1 2 设g 是( g ) = 5 的2 连通外平面图，若e ( g i r a ( g ) 1 ) 屯则 。x 。t ( g ) = 7 证明 对i v ( a ) l 进行归纳 8 1a ( a ) = 5 的2 - 连通外平面图的邻点可区别全染色 若i v ( c ) i = 8 ，则g 是如下四个外平面图之一，同时，下面的图也给出了它们的7 一 a v d t c ，所以此时x m ( g ) = 7 图1 - 3图1 4 假设结论对满足a ( h ) = 5 ，e ( h v a ( 日) 】) 且i y ( 日) l 8 ) 的2 - 连通外平面 图日成立现考虑满r ：a ( g ) = 5 ，e ( g 【吆( g ) 】) 毋且i y ( g ) i = p 的2 连通外平面图g 由 引理1 2 ，分以下四种情形( 其中情形3 是将引理1 2 中的情形3 和4 合并而得到的) ： 情形1 存在 y ( g ) ，使得d g ( 钍) = d a ( v ) = 2 3 u e ( g ) 此时，讨论与定理1 的情形1 相同 以下设g 中任意两个度为2 的顶点均不相邻，且g 是7 种颜色的集合 情形2 存在t ， ，w ，u l ，v l 矿( g ) ，使得d g ) = d o ( v ) = 2 ，d o ) = 4 ，4 曼d a ( v 1 ) d g ( u 1 ) s5 ，“啦， u l o ，让l t j ，v w ， l ， l 叫，札1 吨e ( g ) 令h = g u ，则日是i v ( h ) i = p 一1 的2 一连通外平面图由归纳假设，日有一个7 - a v d t ch 情形2 1 _ d g ( v 1 ) = d o ( t 1 ) = 4 情形2 2 d a ( 1 ) = 4 ，d 。( u 1 ) = 5 此时，阻上两种情形的讨论与定理1 中的情形2 相同 情形2 t 3 d a ( v 1 ) = d g ( 札1 ) = 5 ，设地，t 3 1 ) 一托， ， 1 ) ，u 2 9 情形2 3 1 若以下三条有一条成立： 1 ) d a ( u 2 ) 5 ，如( 让3 ) 5 ； 2 ) “2 与蛳中恰有一个是5 度点且该5 度点的色集合与地的色集合相等； 3 ) 如m 2 ) = d a ( u a ) = 5 ，f l u 2 ，u 3 ，口1 的色集合相等，则 若瓯( “1 ) g ( 口1 ) ，则设g ( u u l ) c g ( 1 ) ；若岛m 1 ) g 岛h ) ，则设g ( u u l ) g 一( k ( u 1 ) 设9 ( ) c c k ( ) 一 9 ( t 1 ) ，g ( u ) e 一 1 ) ，九( w ) ，g ( u u l ) ，g ) ) 对于任意z v ( a ) 1 3e ( a ) 一扣，“钍l ，删， ，设9 ( z ) = h ( z ) ，显然g 是g 的7 - a v d t c 情形2 3 2 若以下两条有一条成立： 1 ) t 2 与中恰有一个是5 度点且该5 度点的色集合与 l 的色集合不等； 2 ) u 2 与u 3 都是5 度点，且它们的色集合中恰有一个与m 的相等 不妨设如池) = 5 但q ( u 。) 瓯( 口) ，且设c 1 g ( u - ) 一c h ( u z ) ，c 2 c h ) 一q p - ) 若c 1 ，c 2 瓯( u 1 ) ，则设g ( u u l ) c c h ( u 1 ) 若c 1 ，c 2 中恰有一个含于繇( 缸，) ，则令9 ( 乱u 1 ) 为另一种颜色 若c 1 ，c 疟c h ( u 1 ) ，则令9 0 1 ) = c 1 ，改h ( u l w ) 为g ( u x w ) = c 2 ，且 i ) 若 ) = c 2 ，则重新定义h ( w ) 为g ( w ) c 一 q ， ( 1 ) ， ( ) ，7 l 1 ) ， ( u l ) ， ( 口t t ，) ) ， 并令可( 删) c 一 九扣叫) ，9 ( t 正i ) ， 扣1 叫) ，9 ( t t 1 ) 。9 ( u l t i j ) ) ； - i i ) 若h ( v w ) = c 2 ，则重新定义 ( 讹j ) 为g ( v w ) e 一 句，t ) ， ( 口) ，h ( v l w ) ，h ( v v l ) ， 并令g ( u w ) c 一 g ( 叫) ， ( 叫) ， l ) ，g ( w 1 ) ，g ( u l t ，) ) ； 令g ) 为异于札1 ，l 和所染的a 中任一种颜色，其它边和顶点若无特别染色， 则颜色不变 情形2 3 3 d o ( u 2 ) = 如( t 3 ) = 5 且啦，撕， 0 1 的色集合互不相同设 c 1 = 玩( 口1 ) ， c 2 ) = 巩( u z ) ， c 3 ) = 矾( 嘶) ，且q ，c 2 ，c 3 互不相同 1 ) 若c 1 ，白，c 3 c k ( 1 ) ，贝0 设g ( u u l _ ) c c k ( u 1 ) ； 2 ) 若c l ，c 2 ，c 3 中恰有两种颜色含于繇(