（运筹学与控制论专业论文）平面图的全染色.pdf

平面图的全染色 摘要 用y ，e ，f ，和否分别表示平面图g 的顶点集，边集，面集，最大度和最小 度若yue 中的元素能用忌种颜色进行染色，使得任意两个相邻或相关联的元 素染有不同的颜色，则称g 是七一全可染的g 的全色数x t ( g ) = m i n k i g 是七一全 可染的) 。显然，给每一个图进行全染色至少要用+ 1 个色，即x t ( g ) + 1 关于图的全染色问题，早在2 0 世纪6 0 年代，v i z i n g 和b e h z a d 分别提出猜 想：对任意图g ，x r ( g ) + 2 这一猜想被后人称为全染色猜想( t o t a lc o l o r i n g c o n j e c t u r e ) ，简记为t c c 随着研究的深入，人们发现很多图类g 不仅满足t c c ， 而且它们的全色数还能取到相应的下界，也就是说x r ( a ) = a + 1 到目前为止， 已经证明对于9 的平面图g ，x t ( g ) = a + 1 但对于4 a 8 的平面图， 人们还未找到非( + 1 ) 全可染的例子于是自然猜想：对于4 的平面图 g ，x r ( g ) = a + 1 是否也成立? t c c 是对任意图的全色数进行猜想，这里是对 平面图的全色数进行猜想，于是我们把这个猜想称作平面图的全染色猜想( t o t a l c o l o r i n gc o n j e c t u r ef o rp l a n eg r a p h s ) ，简称为p t c c 本文围绕著名的全染色猜想( t c c ) 和平面图全染色猜想( p t c c ) ，主要研究 平面图g 的全色数x t ( g ) 运用d i s c h a r g i n g 方法主要证明了 ( 1 ) 若g 是a = 6 且不含4 圈的平面图，则x r ( a ) = 7 ； ( 2 ) 若g 是a = 7 且不含5 一圈的平面图，则x r ( a ) = 8 ； ( 3 ) 若g 是a = 8 且不含带弦的5 一圈的平面图，则地( g ) = 9 ； ( 4 ) 若g 是a = 8 且不含带弦的6 圈的平面图，则x r ( a ) = 9 ； ( 5 ) 若g 是a = 8 且不含相交三角形的平面图，则x r ( a ) = 9 ； ( 6 ) 若g 是a = 8 且不含相邻三角形的平面图，则x r ( a ) = 9 t 关键词：平面图；全染色：最大度；圈 i i t o t a lc o l o r i n go fp l a n eg r a p h s a b s t r a c t f o ra p l a n e g r a p hg ，w e d e n o t ei t sv e r t e xs e t ，e d g es e t ，f a c es e t ，m a x i m u md e g r e e a n dm i n i m u md e g r e eb yv ，e ，f ，aa n d6 ，r e s p e c t i v e l y i fo n e c a nu s e 尼c o l o r st o c o l o ra l le l e m e n t si nvues u c ht h a ta n yt w oa d j a c e n to ri n c i d e n te l e m e n t sr e c e i v e d i s t i n c tc o l o r s t h e ngi ss a i dt ob ek - t o t a l l y - c o l o r a b l e t h et o t a lc h r o m a t i cn u m b e ro f gi sd e f i n e da s ：x r ( c ) = m i n k l ci sk - t o t a l l y c o l o r a b l e o b v i o u s l y , a tl e a s t + 1 c o l o r sa r en e e d e dt oc o l o rg t o t a l l y , t h a ti s ，x r ( c ) + 1 a se a r l ya s19 6 0 s ，v i z i n ga n db e h z a di n d e p e n d e n t l yc o n j e c t u r e dt h a tf o re v e r y g r a p hg ，x t ( g ) + 2 t h i sc o n j e c t u r ew a sk n o w na st o t a lc o l o r i n gc o n j e c t u r e ， i ns h o r t ，t c c t c ci se x t e n s i v e l yr e s e a r c h e di nt h el i t e r a t u r e i ti si n t e r e s t i n gt on o t i c e t h a tm a n yp l a n eg r a p h sa l ep r o v e dt ob e ( a + 1 ) 一t o t a l l y c o l o r a b l e ，i e ，t h ee x a c tr e s u l t h a sb e e no b t a i n e d u pt od a t e ，p l a n eg r a p h sg w i t h 9h a v eb e e np r o v e dt h a t x r ( c ) = + 1 h o w e v e lf o rp l a n eg r a p h sg w i t h4 a 8 ，n oo n eh a sf o u n dt h e c o u n t e r e x a m p l e st h a ta r en o t ( + 1 ) 一t o t a l l y - c o l o r a b l e s o ，w ec o n j e c t u r et h a tp l a n e g r a p h sgw i t h 4a r e ( + 1 ) 一t o t a l l y c o l o r a b l e a sw ek n o w , t c ci sc o n j e c t u r e d f o re v e r yg r a p hga n dh e r et h ec o n j e c t u r ef o c u so np l a n eg r a p h 。t h u s ，w ec a l li tt o t a l c o l o r i n gc o n j e c t u r ef o rp l a n eg r a p h s ，i ns h o r t ，p t c c t h i sd i s s e r t a t i o nm a i n l ys t u d i e sp t c cf o rs m a l l e rm a x i m u md e g r e e ，s a y , = 8 ，7 ，6 i ti sp r o v e dt h a t ( i ) x r ( o ) = 7 ，i fg i sap l a n eg r a p hw i t ha = 6a n dw i t h o u t4 - c y c l e s ； ( i i ) 冶( g ) = 8 ，i fg i sa p l a n eg r a p hw i t h = 7a n dw i t h o u t5 - c y c l e s ； i i i ( i i i ) x t ( g ) = 9 ，i fg i sa p l a n eg r a p hw i t ha = 8 a n dw i t h o u t ( i ) 5 一c y c l e sw i t hc h o r d s ；o r ( i i ) 6 - c y c l e sw i t hc h o r d s ；o r ( i i i ) i n t e r s e c t i n gt r i a n g l e s ；o r ( i v ) a d j a c e n tt r i a n g l e s k e yw o r d s ：p l a n eg r a p h ；t o t a lc o l o r i n g ；m a x i m u md e g r e e ；c y c l e i v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取 得的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或 其他机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的 贡献均己在论文中作了明确的声明并表示了谢意。 作者签名： 亨彤氖 日期： 力。兮年j - 月玎日 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用 影印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不 同方式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在 解密后遵守此协议。 作者签名：亨妃氛导师签名：乏主甬日期：伽7 年r 月玎日 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管 理条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地 和版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：；屯氛 指 导教肌z 乏葫 1 1 基本概念 1绪论 本节定义一些图论的基本术语与符号把一个有序对g = ( ee ) 称为一个 无向图，其中y 是一个有限集合，e 是y 中元素的某些无序对的集合y 中的元 素叫做图g 的顶点，e 中的元素叫做图g 的边通常用y ( g ) ，e ( a ) 分别表示图 g 的顶点集合和边集合，简记为y ，e 用i y f ( 或l a l ) ，l e l ( 或i l a l l ) 分别表示图g 的点数( 又称阶数) 和边数( 又称大小) 任意两个点之间都有边相连的简单图叫 做完全图没有重边和环的图叫做简单图本文研究的图均指有限简单无向图 如果能将图g 画在平面上，使得它的边仅在端点处相交，则称g 是可平面图可 平面图在平面内的任何一个具体的使得边仅在端点处相交的嵌入叫做平面图通 常用f ( g ) 表示平面图g 的面的集合，简记为f 对于图g 的顶点让和u ，若e = 让u e ，则称u 和u 在g 中相邻，或u 和7 3 互为邻点这时又称u 和口是边e 的两个端点，或u 和御分别与e 相关联若g 中的两条边e 1 和e 2 至少有一个公共点，则称e l 和e 2 相邻设g 是一个平面图， ，f ，若g 中的顶点u ，则称点u 与，相关联同样地，对于g 中的边e ，若 e ，则称边e 与，相关联若g 中的两个面 ，2 至少有一条公共边，则称 和，2 相邻设e ，若中任何两条边均不相邻，则称为g 的一个边独立 集，也称为g 的一个匹配 图g 中的一个点边交替序列w = r o e l u l e 2 e k v k 叫做一条途径，其中 e i = ? d i 一1 地e ，1 i k 若v o = y k ，则称训为一条闭途径又若途径? 1 1 上的顶 点v o ，u l ，u 2 ，讥互不相同，则称w 为一条( v o v k ) 路，记作r 称，分别 为路最的起点和终点起点和终点相同的路称为圈路( 圈) 上的边数为路( 圈) 的 长度把图g 中长度为k 的圈叫做七圈k 为偶( 奇) 数时，忌圈叫做偶( 奇) 圈图 g 中最短圈的长度叫做g 的围长，记作9 设u v ，在图g 中与u 相邻的点的全体叫做u 的邻域，记作g ( u ) 称 l g ( u ) i 为点u 的度数，记作d g ( u ) ，简记为d ( 仳) 。把d ( u ) = k 的点叫做k 点类 似地，把d ( u ) k 的点叫做矿点，d ( 钍) k 的点叫做k - _ 点用6 ( g ) 和a ( a ) 分别表示g 中顶点的最小度和最大度，简记为6 ，设图g 是一个平面图，对 1 绪论 于厂f ，用d ( f ) 表示厂的周界( 即按某个方向绕，一周的闭途径) 的长度把 d ( f ) = k 的面叫做七面与顶点类似，可定义矿面和k 一面若一个七面沿着某 个方向的点依次为v l ，v 2 ，讥，则称这个面为( d ( v 1 ) ，d ( v 2 ) ，d ( 仇) ) 一面 对于图g = ( ve ) 和图h = ( v 7 ，e ，) ，若有y 7 ve 7 e ，则称图日是图 g 的一个子图设y y ，把图g 中属于y 7 的顶点以及与y 7 中的点关联的边都 删除所得到的图记作g y 或g y 7 同样地，设e 7 e ，把图g 中属于e 7 的 边都删除所得到的图记作g e 7 或g e 7 特别地，当e ，= u e 时，把g e ， 简记为g 一仳u 对于y 7 y ，把由v 作为顶点集，e = e i e = u u e ，u ，u v ， 作为边集的图叫做g 中由顶点子集y 7 导出的子图，记作a v ，1 同样地，对于 e 7ge ，把由e 7 作为边集，v = _ 【u e l e e 7 ) 作为点集的图叫做g 中由边子集 导出的子图，记作g e 】 若对于图g 中的任意两个顶点u 和u ，g 中都存在一条( u u ) 路，则称g 为连通图，否则称为非连通图非连通图g 的极大连通子图又叫做g 的连通分 支若g 是连通的且不含有圈，则称g 为树由若干棵树所组成的集合称为个 森林，即森林中的每个连通分支是一棵树设t 是一棵树，把t 中的1 点叫做叶 对于非完全图g ，d v v ，若g y 非连通，则称y 7 是图g 的顶点割若 i v 7 i = k ，则称y 7 为g 的忌点割对于g ( 表示阶数为 1 2 的完全图) ，把 图g 中顶点数最少的点割所含的点数称为图g 的连通度，记作k ( g ) 定义的 连通度为竹一1 ，非连通图的连通度为0 若g 满足k ( g ) k 0 ，则称g 是忌。连 通的 文中其它未定义而直接使用的术语和符号请参阅文献【1 1 本节中未介绍的 其它图论术语与符号将在必要时予以阐述 1 2 全染色的研究概况 图论是应用数学的一个重要分支，在管理科学、计算机科学及技术、通信工 程等领域有广泛的应用染色问题是图论中的基本问题，计算机科学及通信工程 中的许多实际应用问题皆以染色问题为基础，比如信道带宽的调度问题等，因此 对染色问题的深入研究有助于这些实际工程问题的解决，也对其它学科的发展有 推动作用随着点染色和边染色的深入研究，图的全染色，即对图的顶点和边同时 进行正常染色，也随之发展起来本学位论文主要研究平面图的全染色问题 2 1 绪论 在2 0 世纪6 0 年代，v i z i n g 2 1 和b e h z a d 3 1 分别给出了全染色的定义和著名 的全染色猜想 定义1 1 若g 中存在一个映射：yue 一 1 ，2 ，耐满足以下三个条件： ( 1 ) 当乱u e 时，有( u ) ( u ) ( 2 )当乱1 u 1 ，札2 耽e ，且u l v l 和u 2 v 2 相邻时，有妒( 也1 u 1 ) 妒( u 2 v 2 ) ( 3 ) 当u 仃e 时，有( u 口) ( 牡) ，妒( 仳u ) ( ) 则称西是图g 的一个( 正常) 尼全染色，或称g 是惫全可染的。定义图g 的全 色数x r ( o ) = m i n k l o 是- 全可染的) 根据全染色的定义，易知x r ( o ) z x + i 。 猜想1 11 2 , a l 对任意的简单图g ，x r ( g ) sa + 2 全染色猜想简记为t c c ( t o t a lc o l o r i n gc o n j e c t u r e ) 实际上，v i z i n g 2 】提出 的是更一般的全染色猜想：对多重图g ，x r ( a ) a + 弘+ l ( 其中p 表示g 的最 大重数) 对于a 2 的图g ，t c c 显然成立1 9 7 1 年，r o s e n f e l d 【4 】和v i i a y a d i t y a 【5 】 用不同的方法证明了 定理1 11 4 , 5 1 对a = 3 的简单图g ，x t ( g ) a + 2 ，即t c c 成立 1 9 7 7 年，k o s t o c h k a 【6 【7 】得到了以下两个结果 定理1 2 【6 l 对= 4 的简单图g ，t c c 成立 定理1 3 吲对a = 5 的简单图g ，t c c 成立 与此同时，不少学者在较大的任意图中对全染色问题进行了研究如 h i l t i o n 【8 】证明了 定理1 4 s l 对a ；l g l 的图g ，t c c 成立 m o l l o y 【9 】证明了 定理1 5 【9 】对充分大的图g ，x t ( g ) a + c ，c 是一个较大的常数 此外，t c c 在平面图类中更是得到了很好的验证 b o r o d i n 【1 0 】得到了 定理1 6 【1 0 】对a 隹 6 ，7 ，8 的平面图g ，t c c 成立 接着，y a p 【11 】和a n d e r s e n 【1 2 】分别证明了 3 1 绪论 定理1 71 1 1 1 2 】对= 8 的平面图g 。t c c 成立 s a n d e r s 和z h a o 【1 3 】合作证明了 定理1 8 【1 3 】对= 7 的平面图g ，t c c 成立 关于图的全染色问题，y a p 在【1 1 】做了系统的总结和研究截至目前，在平面 图类中，t c c 仍未解决的情形是a = 6 在a = 6 确定的基础上再加上一些限制 条件，目前已产生以下的一些结果 吴建良等人【1 4 】证明了 定理1 9 【1 4 】对夕4 的平面图g ，x t ( g ) a + 2 即证明了对a = 6 且不含 3 圈的平面图g ，t c c 成立 王应前和上官敏乐等人【1 5 】证明了 定理1 1 0 【1 5 】对a = 6 且不含4 圈的平而图g ，t c c 成立 本文对这个结果进行了改进，将在第二章证明：对a = 6 且不含4 圈的平 面图g ，x r ( g ) = a + l ，即取到了全色数平凡的下界 陈明和王应前【1 6 】证明了 定理1 1 l 【1 6 】对a = 6 且不含相邻三角形的平面图g ，t c c 成立 最近，侯建锋等人【1 7 】证明了 定理1 1 2 【1 7 】对a = 6 且不含5 圈或不含6 一圈的平面图g ，t c c 成立 接着他们 1 8 】又证明了 定理1 1 3 【1 8 】对= 6 且不含带弦4 一圈或不含带弦5 一圈或不含带弦6 圈的平面 图g ，t c c 成立 随着研究的深入，人们发现很多图类g 不仅满足t c c ，即x r ( a ) + 2 ，而 且它们的全色数还能取到相应的下界，也就是说x t ( g ) = a + 1 王维凡和李国伟对外平面【1 9 】和h a l i n 图【2 0 】的全染色进行了研究，得到 定理1 1 41 1 9 】对a 4 的外平面图g ，x t ( a ) = a + 1 定理1 1 5 2 0 l 对a 4 的h a l i n 图g ，x t ( g ) = + 1 事实上，原文中他们证明这两类图是( + 1 ) 全可选的 张忠辅等人【2 l 】证明了 4 1 绪论 定理1 1 6 【2 l 】对3 的外平面图g ，x r ( g ) = a + 1 1 9 8 7 年，b o r o d i n 等人【2 2 】证明了 定理1 1 7f 2 2 】对1 6 的平面图g ，x r ( g ) = + 1 1 9 8 9 年，他们【1 0 】把这个结果做了改进，得到 定理1 1 8 【1 0 】对a 1 4 的平面图g ，x r ( g ) = + 1 一直到1 9 9 7 年，b o r o d i n 等人【2 3 】又对上述结果进行了改进 定理1 1 9 【2 3 1 对a 1 2 的平面图g ，x r ( g ) = + 1 同年，他们【2 4 】证明了 定理1 2 0 【2 4 】对a 1 1 的平面图g ，x r ( a ) = + 1 2 0 0 7 年，王维凡【2 5 】证明了 定理1 2 11 2 5 对1 0 的平面图g ，x t ( g ) = + 1 近期，k o w a l i k ，s e r e n i 和s k r e k o v s k i 三位学者【2 6 】又证明了 定理1 2 2 嘲对= 9 的平面图g ，x t ( g ) = a + 1 在全染色研究过程中，人们已经找到了3 非( + 1 ) 全可染的例子，如 鲍，( 3 尼+ 2 ) 一圈( 其中k 1 ) ，尬，但未找到4 a 8 非( + 1 ) 全可染的例 子在对正多面图的全染色进行了细致的研究后，王应前等人在“o nt h e7t o t a l c o l o r a b i l i t yo fp l a n a rg r a p h sw i t hm a x i m u md e g r e e6a n dw i t h o u t4 一c y c l e s ( g r a p h s a n dc o m b i n a t o r i c s 接收) 一文中提出了平面图的全染色猜想，简记为p t c c ( t o t a l c o l o r i n gc o n j e c t u r ef o r p l a n a rg r a p h s ) 猜想1 2 对4 的平面图g ，x r ( g ) = + 1 从最大度出发不加任何限制条件，已证明对9 的平面图g ，p t c c 成 立，见定理1 1 6 至定理1 2 2 而当3 时又存在非( + 1 ) 一全可染的例子，于是 p t c c 剩下的情形是4 s8 与= 6 的t c c 问题类似，要解决4 a 8 的p t c c 问题难度很大然而在最大度确定的情况下，加上一些限制条件，已经得 到如下一些比较漂亮的结果 1 9 9 8 年，b o r o d i n 等人【2 7 】证明了 5 1 绪论 定理1 2 31 2 7 】对平面图g ，若满足下列条件之一，则) ( t ( g ) = a + 1 ： ( 1 ) 7 且夕4 ； ( 2 ) a 5 且夕5 ； ( 3 ) a24 且夕6 ： ( 4 ) a 3 且9 1 0 侯建锋等人【2 8 2 9 】证明了 定理1 2 4 【2 8 】对不含4 至k ( k 4 ) 圈的平面图g ，若满足下列条件之一，则 x t ( g ) = + 1 ，即p t c c 成立： ( 1 ) 7 且k 4 ； ( 2 ) 6 且k 5 ； ( 3 ) a 5 且k 8 定理1 2 5 【2 9 】对= 8 且不含5 圈或不含6 一圈的平面图g 。p t c c 成立 近期，刘彬等人【3 1 】 定理1 2 6 【3 0 】对平面图g ，若满足下列条件之一，则x t ( g ) = a + 1 ： ( 1 ) a 6 且不含4 圈和6 圈； ( 2 ) 7 且不含5 圈和6 一圈 事实上，以上定理1 2 3 ，定理1 2 4 和定理1 2 6 ，作者在原文中证明的是 ( + 1 ) 全可选的结果 本文对= 8 ，7 ，6 的p t c c 问题做了进一步的研究，将在以下几章证明： ( 1 ) 若g 是a = 6 且不含4 圈的平面图，则x t ( g ) = 7 ； ( 2 ) 若g 是a = 7 且不含5 圈的平面图，则x t ( g ) = 8 ； ( 3 ) 若g 是= 8 且不含带弦的5 圈的平面图，则x t ( g ) = 9 ； ( 4 ) 若g 是a = 8 且不含带弦的6 圈的平面图，则x r ( g ) = 9 ； ( 5 ) 若g 是= 8 且不含相交三角形的平面图，则x t ( g ) = 9 ；- ( 6 ) 若g 是= 8 且不含相邻三角形的平面图，则) ( t ( g ) = 9 6 2a = 8 的平面图的全染色 文献【2 4 1 1 2 5 2 6 】分别证明了对1 1 ，= 1 0 和a = 9 的平面图g ， ) ( t ( g ) = a + 1 成立对于4 a 8 的平面图要想得到如【2 4 ，2 5 ，2 6 】中那样整 洁的结果比较困难但已有越来越多的平面图被证明是( + 1 ) 全可染的第一 章绪论中提到的定理1 2 3 至定理1 2 4 ，是对具有较小的最大度( 8 ) 的平面 图类进行( 十1 ) 一全染色研究的一些结果侯建锋【2 9 证明了对a = 8 且不含 5 圈或不含6 圈的平面图g ，p t c c 成立本章对a = 8 平面图的+ 1 全可染 问题做了进一步的研究，得到以下几个结论：对8 且不含相交三角形，或不含 相邻三角形，或不含带弦5 圈，或不含带弦6 圈的平面图g ，x r ( g ) = a + 1 ，即 p t c c 成立 2 1a = 8 且不含带弦5 一圈或不含带弦6 一圈的平面图的全染色 t 定理2 1 令g 是一个= 8 且不含带弦5 圈或不含带弦6 一圈的平面图，则 x r ( g ) = 9 假设定理2 1 不成立，令g 是定理2 1 的关于o ( c ) = i v l - i - l e i 极小的一个 反例显然，g 是2 连通的从而g 中没有1 点，且g 的每个面的边界都是圈以 下是反例g 的一些结构性质 引理2 1 酬 ( a )设 1 3 e 若d ) 4 ，则d ( u ) + d ( 口) 1 0 ； ( b ) 令日是g 中所有( 2 ，8 ) 边导出的子图，则日是一个森林 据根引理2 1 ( a ) 可以推出：g 中2 点的两个邻点都是8 点，3 点的邻点是 7 点或8 点，年点的邻点都是6 + 点 设t 是引理2 1 c o ) 中边导出子图日中的一棵极大的树由日的结构性质可 知，t 的所有叶子都是8 点根据数学归纳法可知，t 中存在一个极大匹配m ，使 7 2a = 8 的平面图的仝染色 得丁中的2 一点均被m 所匹配设v 是g 中的一个2 点，v 的邻点设为u 1 钆2 ，不 失一般性，不妨设在m 下u 与u 1 相匹配，此时把u 1 称为2 点”的主点0 称为 主点乱l 的仆点) 主点和仆点的定义最早出现在文献【2 3 】中 引理2 2g 中不含( 4 ，5 ，6 ) 面 证明：假设g 中含有( 4 ，6 ，6 ) - 面f = u l u 2 u 3 ，其中d ( u 1 ) = 4 ，d ( u 2 ) = 6 ，d ( 乱3 ) = 6 由g 的极小性，g ，= g u 1 u 2 是9 全可染的令砂：y ( c 7 ) ue ( g 7 ) 一 1 ，2 ，9 ) 是g 的一个9 全染色抹去心1 的色把在下点乱处所有边所染 的色形成的集合记为s ( 札) ，琴( u ) = s ( u ) u _ 【( 乱) ) 若s ( u 1 ) n 否( 札2 ) d ，则u l u z 的禁用色至多为8 个，所以u l u 2 可染显然，牡1 禁用色也至多为8 个，札1 易染 这样，g 是9 一全可染的，矛盾因此可假定s ( u 1 ) n 君( 札2 ) = 0 不失一般性，设 s ( 札1 ) = 1 ，2 ，3 ) ，琴( 坳) = 4 ，5 ，9 ) ，其中咖( u l i t 3 ) = 3 ，币( 忱u 3 ) = 4 ，妒( u 2 ) = 9 若1 隹否( u 3 ) ，让乱1 “2 染4 ，u 2 让3 改染为l ，从而得到g 的一个9 全染色，矛盾因 此可假定1 否( 仳3 ) 现在，先抹去让l 让3 的色3 ，然后让u l u 2 染3 这样u l u 3 的禁 用色至多为8 个，u l u 3 可正常染好进而，得到整个图g 是9 全可染的，矛盾 引理2 3g 不含图2 1 ( a ) 2 1 ( e ) 所示的构型( 其中标记为的点的度数如图所 示) 证明：假设g 含有图2 1 ( a ) 2 1 ( e ) 所示的构型之一由盯( g ) 的极小性，对v e e ， g = g e 存在一个9 一全染色：v ( g 7 ) ue ( g 7 ) 一 l ，2 ，9 ) 下面分五种 情形讨论： ( 1 ) g 不含图2 1 ( a ) 所示的构型 令e = u l u 3 ，设咖是g ，= g e 的一个9 - 全染色抹去u l 和乱4 的色若 咖( 仳1 u 2 ) 一s ( u 3 ) ，则u l u 3 的禁用色至多为8 个，所以乱1 u 3 可染又因为乱l 和u 4 很容易可以染好，从而g 是9 一全可染的，矛盾因此可假定咖( u 1 u 2 ) 隹否( u 3 ) 不失 一般性，设否( u 3 ) = 1 ，2 ，8 ) ，咖( u 1 u 2 ) = 9 若( u 4 让5 ) 9 ，让u l u 3 染( u 3 锄) ， 把t , 3 t , 4 改染为9 ，从而g 是9 全可染的，矛盾因此，可假定咖( 乱4 1 1 , 5 ) = 9 这时， 首先让u l u 2 ，u 2 u 3 ，u 3 u 4 分别染咖( u 2 u 3 ) ，9 ，咖( “2 如) ，然后让u l u 3 染( u 3 u 4 ) 这样 便得到g 的一个9 全染色，矛盾，说明g 不含图2 1 ( a ) 所示的构型 r 2 = 8 的平面图的全染色 “7 ( d ) jh d i 。 “， ( e ) 图2 1g 中不存在的构型 ( 2 ) g 不含图2 1 ( b ) 所示的构型 令e = u 4 钍5 ，设西是g ，= g e 的一个9 一全染色抹去乱3 i 让5 和的 色若( 札l u 5 ) 否( 讹) ，则u 4 u 5 可染进一步可知，g 是9 一全可染的，矛盾若 ( u l u 5 ) 譬否( u 4 ) ，不妨假定s ( u 4 ) = 1 ，2 ，8 ) ，其中( u 3 u 4 ) = 1 ，( 弛u 6 ) = 2 ( 缸4 ) = 8 ，妒( “l 乱5 ) = 9 现在，若咖( u 6 u 7 ) 9 ，让u 4 u 5 ，u 4 u 6 分别染2 ，9 ，从而 g 是9 全可染的，矛盾因此可假定妒( u 6 u 7 ) = 9 同理，妒( 仳2 u 3 ) = 9 此时，若 咖( 乱1 u 2 ) 1 ，首先让钍1 2 2 染9 ，然后让 2 1 缸5 ， g 2 u 3 染( u 1 乱2 ) ，最后让 u 4 u 5 染9 进 一步可知，g 是9 全可染的，矛盾因此可假定( “l u 2 ) = 1 此时：首先让u 1 乱5 ， u 1 乱2 ，1 上2 u 3 ，缸3 1 l 4 ，u 4 u 6 分别染1 ，9 ，1 ，9 ，l ，然后让 u 4 u 5 染2 ，最后将u 3 ，讹，u 6 染好 色这样便得到g 的一个9 全染色，矛盾，说明g 不含图2 1 ( b ) 所示的构型 ( 3 ) g 不含图2 1 ( c ) 所示的构型 令e = 仳4 u 5 ，设是g 7 = g e 的一个9 一全染色抹去“2 ， u 4 和u 6 的色若 ( u 3 u 4 ) 一s ( u 5 ) ，则札4 u 5 可染将u 2 ，u 4 ，仳6 染好后，便得到g 的一个9 全染色， 矛盾因此可假定咖( u 3 u 4 ) 簪否( u 5 ) 更进一步，可假定否( u 5 ) = j ( 1 ，2 ，8 ) ，其中 ( u 2 让5 ) = 1 ，( 乱5 u 6 ) = 2 ，矽( 让5 ) = 8 ，( 仳3 乱4 ) = 9 若( u l u 6 ) 9 ，让u 5 u 6 染9 ， u 4 u 5 染2 ，从而g 是9 一全可染的，矛盾因此可假定( u 1 u 6 ) = 9 现在，( l u 2 ) ， 0 2 = 8 的平面图i i ：j 五! 染色 咖( u 2 1 2 3 ) 都不为9 ，让u 2 t t 5 染9 ，u 4 奶染1 这样便得到g 的一个9 一全染色，矛盾， 说明g 不含图2 1 ( c ) 所示的构型 ( 4 ) g 不含图2 1 ( d ) 所示的构型 令e = u 6 仳7 ，设西是g 7 = g e 的个9 全染色抹去“2 ，u 4 ，和乱8 的色若妒( 札5 u 6 ) 一s ( u 7 ) ，则“6 u 7 可染将牡2 ，u 4 ，u 6 和u 8 染好色后，便得 到g 的一个9 全染色，矛盾因此可假定( u 5 乱6 ) 譬否( u 7 ) 更进一步，不妨设 一s ( u 7 ) = 1 ，2 ，8 ) ，其中咖( u 4 u 7 ) = 1 ，( u 2 t l 7 ) = 2 ，( u 8 u 7 ) = 3 ，西( u 7 ) = 8 ， 妒( 乱5 u 6 ) = 9 若咖( u 3 钍4 ) 9 ，让“6 u 7 染l ，钍4 7 染9 ，从而得到g 的一个9 一全染 色，矛盾因此可假定矽( u 3 u 4 ) = 9 同理，妒( “1 仳2 ) = 9 此时，( u l u 8 ) 9 让7 2 7 u 8 染9 ，u 6 乱7 染3 ，从而得到g 的一个9 全染色，矛盾，说明g 不含图2 1 ( d ) 所示的 构型 ( 5 ) g 不含图2 1 ( e ) 所示的构型 令e = u 4 u 5 ，设咖是g 7 = g e 的一个9 全染色抹去u 2 ，u 5 和的色 若( 仳1 ) 一s ( u 4 ) ，则u 4 l 5 可染进一步，g 是9 - 全可染的，矛盾因此可假 定i i 5 ( u 1 钆5 ) 譬否( u 4 ) 更进一步，不妨设否( 仳a ) = 1 ，2 ，8 ) ，其中矽( 仳z 乱a ) = l ， 妒( 让3 u 4 ) = 2 ，( u 4 乱6 ) = 3 ，妒( u 4 ) = 8 ，( u l u 5 ) = 9 若砂( u 2 牡3 ) 9 ，让u 2 7 2 4 染 9 ，u 4 u 5 染1 ，从而得到g 的一个9 。全染色，矛盾因此可假定( 1 t 2 u 3 ) = 9 同 理，咖( 铆) = 9 若( 札1 让2 ) 2 ，首先交换u 2 u 3 与 u 3 u 4 的染色，然后让u 4 u 5 染2 ，从而g 是9 全可染的，矛盾因此可假定咖( u 1 乱2 ) = 2 此时，首先让路 p = 乱5 u l u 2 u 3 u 4 u 6 中的边依次染2 ，9 ，2 ，9 ，2 ，然后让u 4 u 5 染( “4 u 6 ) ，便得到g 的一个9 全染色，矛盾，说明g 不含图2 1 ( e ) 所示的构型 下面将根据g 所具有的结构性质，运用权转移方法完成定理2 1 的证明 首先，由握手引理d ( u ) = 2 1 e l ，边数与面数的关系d ( f ) = 2 1 e i 以及 v e v f 平面图的欧拉公式i y i 一 e i + i f i = 2 可得 ( 2 d ( 口) 一6 ) + ( d ( ，) 一6 ) = - 1 2 y e f l o 2 = 8 的平面图的全染色 其次，给罔g 的顶点t ，分配权c h ( v ) = 2 d ( v ) 一6 ，给g 的而，分配权 c h ( y ) = d ( s ) 一6 ，则有 c ，t ( z ) = - 1 2 t y u f 现在我们将根据下述的权转移规则，重新分配顶点和面的权，使得对每一个 元素z vuf 都有c ，。7 ( 。) 0 这里c ，。( 。) 为重新分配权以后顶点或面z 的新 权因为只是在图g 的点和面之间进行权转移，故转移前后权的总和应该保持不 变从而有0 c h ( z ) = c h ( x ) = - 1 2 ，矛盾，说明极小反例g 不存在， z y u f z y u 从而定理2 1 成立 下面是重新分配顶点和面的权所需要的规则： r 1 ：给2 点口的权 由引理2 。l ( a ) 知，v 只与8 点相邻每个与u 相邻的8 点转l 给u r 2 ：给3 而，的权 r 2 1 若，是一个( 3 一，7 + ，7 + ) 一面，则每个与，相关联的7 + 一点转；给， r 2 2 若厂是一个( 4 ，6 + ，7 + ) - 而，则与，相关联的4 - 点转互1 给，；与，相关联 的6 点( 由引理2 2 知，3 面上至多有一个6 点) 转1 给，；每个与，棚关联的7 + 点转g 给， r 2 3 若，是一个( 5 + ，5 + ，5 + ) 面，则每个与，相关联的5 + 一点转1 给， r 3 ：给4 一面，的权 r 3 1 若，与两个3 - 点相关联，则与，相关联的另外两个顶点为7 + - 点每 个7 + 点转l 给， r 3 2 若，仅与一个3 - _ 点相关联，则，上与此3 - _ 点相邻的两个点为7 + 一点 每个这样的7 + 一点转i 给，；，上剩下的那个4 + 一点转i 1 绎， r 3 3 若，不与任何3 - 点和关联，则每个与，相关联的4 + 一点转互1 给， r 4 ：给5 面，的权 r 4 1 若，与两个3 - _ 点相关联，则与，相关联的其余三个点为7 + 一点每个 2a = 8 的平面图的全染色 7 十一点转i 1 给， r 4 ，2 若，仪与一个3 一点相关联，则每个与f 相关联的4 + 一点转；给厂 r 4 3 若，不与任何3 一点相关联，则每个与，相关联的4 + 一点转i 1 给， r l r 4 8 点2 点 8 点 r i 3 - - 点4 点4 点5 - 点 7 乞点7 + 点6 _ 点7 + - 点7 + 点 r 2 1r 2 2 3 ：点7+点3-点7 - 点 7 + 点5 + 点5 + - 点 r 2 3 4 i 点4 1 点 口圆囡 7 - 点 3 - 点 r 3 1 3 - - 点 7 + 点 7 - 点4 1 点 r 3 2 3 - - 点 4 点4 + 点 r 3 3 4 + 点 7 - 点3 - 点 4 + 点 4 + 点4 - 点4 + 点4 + 点 r 4 2r 4 3 图2 2 权转移规则 详细的权转移规则见图2 2 总结以上权转移规则，特别有： 注l 7 + 一点不转权给与其相关联的6 + 一而；7 + - 点至多转 给与其相关联的 5 一面；至多转l 给与其相关联的4 一面；进一步，。7 + 一点转i 给与其相关联的只含一 个3 一点的4 一面，见r 3 2 验证新权 1 2 2 = 8 的平面图的仝染色 由以上权转移规则可知，对g 巾的每个而厂均有c 九( ，) 0 成立，且对所有 的2 点口，c h ( 钉) 0 也成立下面只需验证g 中3 + 点的新权 设u 为3 点由权转移规则知，3 点既没有转出权也没有接收权，因此 c h ( u ) = c h ( v ) = 0 设u 为4 点由r 2 2 ，r 3 2 ，r 3 3 ，r 4 2 和r 4 3 知，v 至多转百1 给每个相关联 的面，；k - n 町c h ( v ) c h ( v ) 一；4 = 0 设v 为5 点注意到g 不含带弦5 圈或带弦6 圈，钳至多关联三个3 而由 r 2 3 ，r 3 2 ，r 3 3 ，r 4 2 和r 4 3 知，c h 7 ( ) c h ( v ) 一1x3 一互1 2 = 0 设u 为6 点由权转移规则知，u 至多转1 给每个相关