（运筹学与控制论专业论文）图的边染色与列表边染色.pdf

摘要 图的边染色与列表边染色 摘要 g = ( ke ) 表示一个顶点集y ，边集e 的有限简单无向图g 的 一个正常南一边染色是一个映射q o ：e - 1 ，27 ，后 使得相邻边染 不同的色如果g 有一个正常七边染色，则称g 是七边可染的。g 的 边色数( g ) 是使得g 有正常七边染色的最小整数k 图g 的一个边色列表是一个颜色集合簇l ，它指定g 的每条边e 一 个颜色集合l ( e ) 若g 有一个正常的边染色妒，使得对每一条边e e ， 妒( e ) l ( e ) ，则称g 为l - 边可染若对任意l 满足j l ( e ) j = 。k ，对任何 边e ，g 是l - 边可染，则称g 是七边可选择的。g 的边列表色数：或边 选择数( g ) 是使得g 是七边可选择的最小整数k ， v i z i n g 在1 9 6 4 年证明：若g 是简单图，则z x ( a ) ) ( 7 ( g ) sa ( c ) + 1 ，其中( g ) 为g 的最大度称x 7 ( g ) = ( g ) 的简单图为第一类，否 则，称为第二类 本文在前人的工作基础上继续研究平面图的分类和边选择性问 题，证明了： ( 1 ) ( g ) = 6 ，且不含弦5 圈的平面图g 是第一类 ( 2 ) ( g ) = 5 且不含相交三角形的平面图g 是第一类 ( 3 ) 若( g ) = 6 ，且x ( r ) o 的图g 满足下列条件之一，则g 是 第类： ( i ) 不含相邻三角形： ( i i ) 不含弦5 圈和弦6 。圈 ( 4 ) 若g 是一个a ( o ) 5 ，且不含弦5 圈的平面图，那么g 是 ( ( g ) + 1 ) 边可选的 ( 5 ) 若平面图g 满足下列条件之一，则g 是( a ( g ) + 1 ) 边可选 摘要 的： ：a ) 不含弦4 一圈和弦5 一圈； ( b j 不含弦5 一圈和弦6 - 圈 关键词：平面图，边色数，边选择数，最大度 a b s t r a c t e d g ec o l o r i n ga n dl i s te d g ec o l o r i n go f g r a p h s a b s t r a c t l e tg = e ) b ea f i n i t e ，s i m p l ea n du n d i r e c t e dg r a p hw i t h t h ev e r t e x s e tva n dt h ee d g es e te ap r o p e rk - e d g e - c o l o r i n go f gi sa m a p p i n gf r o m e i n t o 1 12 ，忍 s u c ht h a tn oa d j a c e n te d g e sr e c e i v et h es a m ec o l o r i f gh a sa p r o p e rk - e d g e c o l o r i n g , t h e ng i ss a i dt ob ek - e d g e - e o l o r a b l e t h e c h r o m a t i ci n d e x , d e n o t e db yx 7 ( g ) ，i st h el e a s ti n t e g e rks u c ht h a tgi s k - e d g e - c o l o r a b l e a ne d g e - l i s t - a s s i g n m e a t o fgi sas e to fl i s t so fc o l o r sw h i c ha s - s i g n se a c he d g eeo fg al i s to fc o l o r sl ( e ) i fgh a sap r o p e re d g e c o l o r i n g 妒s u c ht h a tq o ( e ) l ( e ) f o re v e r ye e t h e ngi ss a i dt ob e 工- c o l o r a b l e i fgi sl c o l o r a b l ef o re v e r ye d g e - l i s t - a s s i g n m e n tlw i t h i l ( e ) l = 知f o re v e r ye et h e nw es a yt h a tg i sk - l i s t - e d g e - c o l o r a b l e ，o r 七- e 也e - c h o o s a b l e t h ee d g ec h o i c en u m b e r , o r l i s t - c h r o m a t i ci n d e xo fg ， d e n o t e db y “( g ) ，i st h el e a s ti n t e g e rks u c ht h a tgi sk - e d g e - c h o o s a b l e i n1 9 6 4 ，v i z i n gp r o v e dt h a te v e r ys i m p l eg r a p hgh a sl x ( c ) sz ( g ) a ( c ) + 1 ag r a p hg i sc l a s sli fx 7 ( g ) = ( g ) ，a n dc l a s s2o t h e r w i s e i nt h i st h e s i s ，w ep r o v et h ef o l l o w i n gr e s u l t s ： ( 1 ) i f g i s a p l a r m r g r a p h w i t h m a x i m u m d e g r e e 6 a n d w i t h o u t c h o r a l - 5 - c y c l e s ，t h e ngi so f c l a s s1 ( 2 ) i f g i sap l a n a rg r a p hw i t hm a x i m u md e g r e e5a n dw i t h o u ti n t e r - s e c t i o nt r i a n g l e s ，t h e ngi so f c l a s sl ( 3 ) l e t gb ea g r a p h w i t h m a x i m u m d e g r e e6 a n dx ( z ) 0 g i s o f c l a s s1i f o n eo f t h ef o l l o w i n gc o n d i t i o n sh o l d s ： ( i ) gc o n t a i n sn oa d j a c e n tt r i a n g l e s ； 一i 一 a b s t r a c t ( i i ) gc o n t a i n sn oc h o r a l - 5 一c y c l e sa n dc h o r a l - 6 一c y c l e s ( 4 ) i fg i sa p l a n a rg r a p hw i t hz x ( g ) 5a n dw i t h o u tc h o r a l - 5 一 c y c l e s , t h e ng i se d g e - ( a ( g ) + 1 ) c h o o s a b l e ( 5 ) l e t gb eap l a n a rg r a p h gi se d g e 一( a ( g ) + 1 ) - c h o o s a b l ei f o n e o f t h ef o l l o w i n gc o n d i t i o n sh o l d s ： ( a ) gc o n t a i n s1 1 0c h o r a l - 4 - c y c l ea n dc h o r a l - 5 - c y c l e ； ( b ) gc o n t a i n sn oc h o r a l 一5 一c y c l ea n dc h o r a l - 6 一c y c l e k e yw o r d s ：p l a n a rg r a p h ，c h r o m a t i ci n d e x , l i s t c h r o m a t i ci n d e x , m a x i - m u m d e g r e e i v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 一签名碱录球眺岬协w 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 一签名印春录球翩躲王帆吼炒7 、肌，纱 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：7 系永五牡 指导教师：撕 一、绪论 ( 一) 、基本概念 一、绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号 一个无向图是一个有序对g = ( k e ) ，其中y 是一个有限集合，e 是矿中 的不同元素的无序对的集合y 中元素叫做图g 的顶点，露中元素叫做图的边 通常用矿( g ) ，e ( e ) 分别表示图g 的顶点集合，边集合用i g i ，l i g l l 分别表示 g 的顶点数和边数边数为o 的图称为空图没有重边和环的图日q 做简单图除 非特别指出，本文研究的图均指简单无向图对于图g 中的顶点和口，若边 e = u 口e ( g ) ，则称t 和u 相邻，“和u 互为邻点；称u 和u 是e 的端点，u 和 分别与e 关联若g 的边e 和，有一个公共端点，则称e 和，相邻，在图g 中与 顶点让相邻的顶点的全体叫作“的领域，记作g ( “) ；并把g 【u l = n g ( u ) u u 称作点t 的闭领域称l g ( 牡) j 为顶点珏的度数，记作d g ( u ) g 所有顶点的度 中，最大者和最小者分别称为g 的最大度和最小度，记作a ( g ) 和6 ( g ) 在不 产生混淆的情况下，我们把v c c ) ，e ( g ) ，n a 缸) ，n a u l ，d e ( u ) ，a c g ) ，6 ( g ) 分别简 记为k e ，( u ) ，阻】，d ( “) ，5 若d ( v ) = k ( d ( v ) k ，d ( v ) s ) ，则称口为一个 k 点( 矿点，k - - 点) 我们把一个与u 相邻的点，叫作口的一个邻点用呶0 ) 表示 的邻点的个数 如果能将图g 画在某个曲面上，使得它的边仅在端点处才可能相交，图的这 种画法称为图的曲面嵌入若图g 能够平面嵌入，则称图g 是可平面图可平 面图的一个平面嵌入称为平面图设g 是一个图的曲面嵌入，我们常用f ( a ) 表 示面集合对于，f ( g ) ，用b ( i ) 表示组成面，的闭途径若1 ，u 2 ，u 。是 b ( f ) 上按顺时针排列的点，我们就记，= u l ，u 2 ，1 称点u l ，地，与 面，关联，把途径6 ( ，) 的长度称为面，的度记为d ( ，) 若d f f ) = k ( d ( f ) k ， d f f ) 后) ，则称，为一个一面( 矿一面，k - - 面) 若一个面的边界是一个圈，则称这 个面是一个简单面若g 是2 连通的，刚它每个面的边界都是一个圈对于3 面 ，= 陋t z 2 2 3 】，为强调它的关联特性，常用度序列( d ( x t ) ，d ( x 2 ) ，d ( 黝) ) 表示，即可 称面，为( d 0 1 ) ，d ( x 2 ) ，d ( z 3 ) ) - 面 一圈c 是指图g 中长为k 的圈，若z ，y y ( g ) ， 则称x y e ( c ) e ( g ) 为圈c 的弦至少存在一条弦的- 圈称为弦- 圈，或称 为网 一、绪论 一个曲面e ，令x ( ) 表示的欧拉示性数熟知平面图的欧拉示性数等于 2 本文所用术语和符号基本上与文献 1 】中一致本节中未介绍的其他图论术 语将在必要时予以阐述 ( 二) 、边染色问题的研究概况 图的染色理论是图论中最重要的分支之一，在无线通讯频道分配、舰队维 护、任务分派、交通定向等诸多领域都有着广泛的应用，见文献( 2 】本学位论文 主要研究图的边染色与列表边染色 图g 的一个正常女一边染色是一个映射妒：e ( c ) 一 l ，2 ， ，使得每一对 相邻边z 和y ，有妒 ) 妒0 ) g 的边色数x ( g ) 是使得g 有一个正常一边染色 的虽小整数k 如果g 有一个正常k 边染色，则称g 是k 边可染的，除非特别声 明，图g 的k 边染色均指正常k 边染色 关于图的边染色问题，1 9 6 4 年，v i z i n g 给出了如下著名定理： 定理1 1i a 若g 是简单图，则 z x ( c ) x ( g ) s ( g ) + 1 满足x ( g ) = a ( c ) 的简单图g 称为第一类；否则，称为第二类在将近半个 世纪的漫长岁月里，人们一直在为解决简单图的分类问题做着不懈的努力解决 一般图的分类问瓢相当困难，因此人们关心平面图等特殊圈的分类问题对于外 平面图来说，问题已完全解决，见下面的定理1 2 定理121 4 l 外平面图是第二类图，当且仅当它是一个奇圈 对一般的平面图，早在1 9 6 5 年，v i z i n g 就证明了下述重要的结果 定理1 3 5 1 ( g ) 8 的简单平面图g 是第一类 1 9 6 8 年。他提出了如下著名的平面图猜想： 猜想1 1 4 1 ( 平面图猜想) 最大度为6 或7 的简单平面图是第一类 时隔三十多年之久，z h a n g ( 2 0 0 0 ，【7 1 ) ，s a n d e r s 和z h a o ( 2 0 0 1 ， 8 1 ) 独立地证明 了：( g ) = 7 时平面图猜想成立即有 一2 一 一、绪论 定理1 41 7 , 8 l 最大度为7 的平面图是第一类 其它学者对上述一些结果进行了改进：文献【9 】9 证明满足下列两个条件之一 的图g 是第一类：( 1 ) 8 ，x ( ) o ；( 2 ) a 之9 ，x ( ) 一1 文献【l o 】证明： a 7 ，x ( ) 0 的简单图是第一类 在平面图的分类问题中，对于a 7 的平面图，已经完全确定它们都是第一 类，对于= 6 ，猜想还未解决对于 2 ，3 ，4 ，5 的平面图，在【5 】中，v i z i n g 举 例说明既存在第一类又存在第二类图因此，给出t 2 ，3 ，4 ，5 的平面图是第一 类或第二类的特征刻画，在平面图的分类中也具有重要意义对a = 2 的平面图 的分类问题已经完全解决，即所有的奇圈都是第二类，所有的偶圈和路都是第一 类对3 的平面图，1 9 7 4 年sf i o r i n i 证明了如下定理： 定理1 , 5j i l l 如果平面图g 满足下列条件之一，那么g 是第一类其中9 表示平 面图的围长 ( i ) 3 ，9 8 ( i i ) 24 ，9 5 ( i i i ) a 5 ，9 4 ( i v ) 8 ，g 3 1 9 9 9 年，p l a m 等人证明了如下结果： 定理1 6 1 2 1 若平面图g 满足下列条件之一，则g 是第一类 ( 1 ) 5 且g 不含4 - 圈和5 圈 ( 2 ) a 5 ，g 不含4 圈，并且g 中不含相交三角形 ( 3 ) 4 且g 不含4 n 1 4 圈 ( 4 ) 4 ，g 不含4 、5 、6 - 圈，并且g 中不含相交三角形 对于a = 6 的情况，许多学者给出第一类图的一些充分条件2 0 0 3 年，周国飞 证明了： 定理1 7 1 3 1 a ( c ) = 6 且不含有k 圈( 对某个k 3 ，4 ，5 ) 的简单平面图g 是第 一类 新避h 月华和王维凡给出了如下结果 一3 一 一、绪论 定理1 8 【1 4 】设g 是最大度为6 的平面图，如果它满足以下条件之一，则g 是第 一类( 1 ) g 不含弦4 - 瞄；( 2 ) g 不含弦5 一圈和弦6 - 圈；( 3 ) g 不含6 圈 2 0 0 6 年。李学超等人在文献【l5 】中对定理1 7 的结果进 亍了改进，证明如下 的结论：a = 6 的简单图g 若满足下列三个条件之一，则g 是第一类：( 1 ) 不含 3 圈，( ) 2 - 3 ；( 2 ) 不含4 一圈，x ( ) - 3 ；( 3 ) 不含5 一圈，x ( ) 2 - 1 列表边染色是边染色的推广映射二称为图g 的一个边色列表，如果它指定 g 的每务边e 一个颜色舆合l ( e ) 若g 有一个正常的边染色协使得每一条边e 满足妒( e ) l ( e ) ，则称g 为l 一边可染的，或称妒是g 的一个l - 边染色若对每 一条边e e ( g ) ，都有 ( e ) i = k 成立，且g 是己一边可染的，则称g 是k - 边可 选择的g 的边选择数，或者列表边色数x i ( c ) 是使得g 是k 一边可选择的最小整 数k 下面介绍两个著名的列表边染色猜想： 猜椽1 2i t ( ；1 如果g 是一个多重图，则x i ( e ) = 髟( g ) 这是著名的i 。c c 猜想对于二部莺图 1 7 】、奇阶完全图 1 8 1 、多重圈0 9 1 、外 平面图 2 0 1 、1 2 可嵌入非负特征曲面上的图【2 1 1 等，已证明猜想1 2 成立但 是对于大多数图类，猜想1 2 是否成立未得到验证v i z i n g 提出了下面弱化的列表 边染色猜想【见文献【2 2 】) ： 猜想1 3 每一个简单图g 是( 十1 ) 一边可选的 h a 币s j 于1 9 8 4 年证明：如果g 是一个23 的图，那么x ，( g ) 2 a 一2 这 隐含着猜想l3 对a = 3 的图成立，j u v a n ，m o h a r 和雪k r e k o v s k i l 2 4 1 解决了= 4 的 情形对于完全图【1 8 l ，团长至少为8 a ( i n a + 1 1 ) 的图口“，9 的平面图【2 5 l 等， 已证明猜想i 3 成立设3s 自6 是一个固定整数，对于不舍一圈的平面图瞄- 2 9 1 ， 猜想1 3 成立王维凡和李国伟p 0 1 证明：每一个a 5 且没有相交三角形的平面 图是( + 1 ) 边可选择的 ( 三) 、本文的主要结果 本学位论文主要围绕猜想1 1 和1 3 ，对一些图类进行研究，以验证该猜想成 立 在第二章中，我们绘出第一类平面图的若干充分条件，证明下列两个结论： ( 1 ) a = 6 ，且不含弦5 一圈的平面图g 是第一类； 一直一 一、绪论 ( 2 ) = 5 且不含相交三角形的平面图g 是第一类 在第三章中，从平面图推广到欧拉特征值非负的一般曲面上，从而改进了b 月华和王维凡在文献 1 4 】中的结论，证明：对于a = 6 ，且x ( ) 0 的图，若满足 下列条件之一。是第一类： ( 1 ) 不含相邻三角形； ( 2 ) 不含弦5 圈和弦6 圈 在第四章中，我们研究了平面图g 的列表边染色，并证明如下两个结论： ( 1 ) 若平面图g 满足a 5 ，且不含弦5 - 圈，那么g 是( + 1 ) 边可选的 ( 2 ) 若平面图g 满足下列条件之一，则g 是( + 1 ) 边可选的：( a ) 不含 弦4 一圈和弦5 - 圈；( b ) 不含弦5 圈和弦6 圈 = 、平面髑鲍边染色 ( 一) 、预备引理 二、平面图的边染色 对于平面图猜想，最大度为7 的情形已被彻底解决，可参考文献【7 】f 8 1 最大 度为6 的情形，目前仍然是一个公开问题该问题目前尽管还没有被解决，但已经 取得一些进展，参考文献【1 3 】【1 4 1 本章在前j 的基础上给出了最大度为6 和最大 度为5 的平面图是第一类的充分条件 研究图的分类问题的一个重要途径是去研究“色临界图”的结构性质若连 通图g 本身是第二类，但去掉任意边e 后是第一类，则称g 是色l 胨界图最大度 为k 的临界图简称k 临界图显然，每个k 一临界图( k 2 ) 是2 一连通的以下是有 关色临界图结构性质的四个引理这四个； 理在以后的章节中也要用到，不再重 复给出， 引理2 1 s l ( v i z i n g 邻接性引理) 设g 是一个- 临界图且 3 v 那么 ( 1 ) 口相邻至少两个一点； ( 2 ) 如果靠( t ) i ，七a ，那么d ( 口) 2 一岛+ 1 引理2 2 门( z h a n g 邻接性g 【理) 设g 是一临界图，x y e 使得d ( z ) + d ( y ) = + 2 那么 ( 1 ) 每一个u n 协，影) 。， 是一点： ( 2 ) 每一个u n ( n ( x ，) ) f 。， 满足d ( v ) 2a l ； ( 3 ) 如果d 0 ) ，d ( y ) ，则每一个 n ( n 仁，蓼) ) ( z ，y 是点 引理2 3 3 1 1 设g 是，临界图假设z 是一个3 。点，相邻三个点，那么必存在 一个点0 ) ，使得对任意的。n ( v ) 扛) ，都有d ( z ) 1 引理2 4 g l 如果图g 包含三个不同的点3 ，t ， 满足下列两个条件，那么g 不是 临界图 ( 1 ) ，w 0 ) ，且d ( w ) 2 a d ( 8 ) 一d ( t ) + 2 ； ( 2 ) 8 w 含在至少d ( 8 ) + d ( ) 一a 一2 个三角形中，且t 不是这些三角形的项 点 一6 一 二、平面图的边染色 对于图g 的曲砸嵌入，假设g 不含弦5 圈，那么下面三个引理成立，且这三个 引理在证明后面各章的结论时也经常用到，以后出现不再重复证明 引理2 5 若图g 不含弦5 - 圈，则g 中不存在3 面相邻两个非相邻3 - 面 证明：假设引理2 5 不成立，那么g 存在3 一面，2 = z y z 】相邻两个非相邻3 面 ，l ，磊，记为，1 = k 盼l 和矗= i ：m , 1 因为g 是简单图且五与盎不相邻，所以 口，t ，u 聋叠，玑z 此时，一个5 一圈螂z 。带弦正存在，矛盾 引理2 5 暗示每个5 一点至多关联三个3 一面，每个6 点至多关联四个3 面 引理2 6 若图g 中不含弦5 - 圈，则g 中不存在3 面，相邻一个4 面，”使得 i e c f ) ne ( ，”) i = 1 证明：假设g 邑$ - 4 一面，”= z y z u l 相邻3 一面，= k 】，使得e ( f ) ne ( i ”) = 铷讣注意到g 是简单图，可推知口聋b ( f ”) 且一个5 圈x v y z u x 带弦x y 存在，矛 盾引理得证 引理2 6 暗示：如果4 - 面，”与3 一面，7 相邻，那么l e ( f ”) n e ( f ，) | = 2 ，即 b ( f ”) nb ( f 7 ) 包含一个2 一点而且，由于g 是简单图，每个4 - 面至多相邻一个3 一面 g 的子图c 称为一个丛，如果c 是一个非空极小3 一面的集合，使得g 中没有 其他的3 - 面相邻c 的成员若一个丛由k 个3 面组成，则称为女丛。如果面，相 邻于c 的某个成员，且，芷c ，那么称，与丛c 相邻若，与c 相邻于边e ，则可 用丘表示面， 下面的引理由引理2 5 直接可得 引理2 7 若图g 不含弦一5 圈，则下面的结构穷举了g 中所有可能的丛( 见图1 ) c 1 ：一个3 - 面： c 2 ：两个相邻3 - n ： 岛：三个相互相邻3 面 一7 一 二、平面图的边染色 y j z c 1 c 2c 3 图1g 中所有可能的丛 ( 二) 、第一类图的两个充分条件 为了方便下面定理的证明，首先我们绘出如下说明：对一个6 临界图g 和 u v ( g ) ，根据引啦1 ，下面结论( p 1 ) - ( p 5 ) 显然成立，且结论( p 1 ) - ( p 5 ) 在第三章也 将用到，不再重复给出 ( p 1 ) 如果d ( v ) = 2 ，那么v 相邻两个6 - 点， ( p 2 ) 如果d ( v ) = 3 ，那么u 只能相邻5 + 一点；且若d s ( v ) l ，则d 6 ( u ) 2 ， ( p 3 ) 如果d ( v ) = 4 ，那么u 只能相邻4 + 一点；且若d a ( v ) = 1 ，则d 6 ( v ) = 3 ；若 d 5 0 ) 21 ，则d b p ) 2 ( p 4 ) 如果d ( v ) = 5 ，那么 只能相邻3 + - 点；且若d 3 ( v ) = l ，则如( ”) = 4 ；若 d 4 ( 口) 1 ，则d 6 ( ) 23 ( p 5 ) 设 是一个6 一点若d 2 ( u ) = 1 ，则d b ( ) = 5 ；若d 3 ( ) l ，则d 6 ( 口) 24 ； 若d 4 ( 口) 1 ，则d 6 ( u ) 23 定理2 1 设g 是一个= 6 且不含弦5 圈的平面图，则g 是第一类 证明：假设定理21 不成立，那么g 是第二类图不失一般性，假设g 是6 - 临界 图易见g 是2 连通的 在图l 中观察丛c 3 ，不失一般性，假设d ( x ) d ( y ) sd ( 。) 由定义可知 d ( u ) = 3 再根据( p 2 ) 和引理2 1 ，有d ( x ) 5 ，d ( y ) = d ( z ) = 6 当d ( x ) = a = 5 ，6 ) ，我们可记c 3 为鹾” 由e u l e r 公式 l y ( g ) i i e ( g ) i + i f ( g ) = 2 8 一 。 二、平面图的边染色 和关系式 d o ) = d ( ，) = 2 i e ( g ) w v ( g )i e f ( g ) 推出 ( d c v ) 一4 ) + ( d ( ，) 一4 ) = _ 8 q y ( g )i e f ( g ) 任意$ v ( g ) uf ( g ) ，定义权函数w ( x ) = d ( x ) 一4 ，于是g 的所有顶 点和面的权和等于一8 我们将重新分配这些权使得总和不变，但是对每个 z v ( c ) uf ( g ) ，有新权 ( z ) 0 ，于是有下面矛盾不等式 0 ( 。) = 坩( z ) = 一8 v ( g ) u f ( g )z e v ( o ) u p ( g ) 从而证明假设不成立，定理为真 任意口y ( g ) ，令r ( ) 表示与 关联的所有3 一面的集合对于6 一点 ，进 一步定义t 7 ( 口) ：如果d a ( v ) = 1 ，d 4 ( v ) = 0 ，且口关联一个丛c j ”，或者如果口关 联丛c 5 5 ，那么用r ( 口) 表示t ( v ) 中不在碟”a = 5 ，6 ) 中的那些三角形的集合； 否则，我们令r 0 ) = 丁 ) 同时记( u ) = j t ( u ) i 和( u ) = i t 0 ) 1 显然，如果 d zc v ) = 1 ，d 4 ( ) = 0 ，且u 关联丛c r ，或者如果 l j 关联丛a ”，那么( ) 0 ，那么，转移权厣( ，) 给可能相邻的3 一面 对于蜀y ( g ) uf ( g ) ，令t ( x 一口) 表示根据权转移规则( r 1 ) 一限4 ) ，元素 转给掣酌权量 断言1 设u 是一个6 - 点，t 7 ( ”) 由规则( r 1 ) ，下面表格给出了所有可能的 r 0 一，) 值( 表格中，( 口) ，d 2 ( v ) 和d 3 ( u ) 中的字母 被省略) r 0 一，) 之 亡，= lf = 2t 7 = 3 t 7 = 4 d 2 = 如= 0 21 2 3v 2 d 2 = 1 ，d 3 = 0 1 1 2 1 3 1 4 d 2 = 0 ，如= 2 4 z 2 3 4 ，9 1 ，3 d 2z0 ，d 3 = l ，f 7 = t 5 3 5 6 5 9 5 1 2 d 2 = 0 ，d 3 = l ，t 7 ，因此，r ( c ) + 1 + = 嚣3 2 若d ( 。) 5 ，因为d 3 ( ) s1 ，所以7 r 0 一c ) 2 击= ，当d ( 。) = 5 ，有 d a ( z ) = 0 且r 0 一c ) 2 当d ( 。) = 6 ，有d 3 ( z ) l 且r ( z c ) 啬综上 分析，推出r 0 一c ) m i n 暑， = 类似地，我们有r 扣一c ) 最后， t ( c ) + ；+ 2 ；= 面2 3 二、平而图的边染色 2 3 d 0 ) = 5 此时，c l ( y ) 25 ，d ( z ) ，d ( v ) 3 ，d 2 ( ) = d 2 ( v ) = d 2 ( z ) = 0 由于d ( 丘。) ，d ( 矗。1 ， d ( 凡，) ，d ( 五。) 25 ，那么c 从它所有的邻面至少获得权 如果d ( u ) = 5 ，那么 d 3 ( z ) = d 3 ( y ) = o ，可知r 扛一c ) 2 = ；类似地r 国一c ) ；最后， r ( c ) + 2x ；= 嚣+ 如果d ( ) = 6 ，那么f 白一c ) 2x 杀= 若d ( z ) = 3 由( p 4 ) 可知 d ( v ) = 6 ，因此观察表1 和表2 ，r 0 一c ) 乏2 ；= 3 ，r 0 一c ) 啬 ，最厣， f ( c ) i 4 + + 5 4 + = 面3 7 7 若4sd ( z ) 5 ，则d 3 ( x ) = 0 ，丁缸一c ) 2 = ；， 因此，r ( c ) + ；+ ；= 面3 1 若d ( z ) = d ( v ) = 6 ，则点。和 各转移权至少蠢给 c ，最后有，f ( c ) ；+ 2 杀+ i = 2 2 4 d ( 神= 6 我们对d ( z ) 进行讨论，分如下五种子晴形： ( 2 4 a ) 假设d ( z ) = 2 ，此时d ( v ) = 6 ，d ( 丘。) ，d ( 厶) 25 ，而且厶：与厶，表示 同一个面丘。和知各转移权至少 给c 由于 至多关联三个3 一面，由表1 ， 7 7 ( u + c ) 三= ；同列+ 注意至( z ) = t ( 茁) ，矿( f ) = ( ) 如果d ( 丘。) = 4 ，根据引理26 t ( z ) s3 ，t ( y ) 3 因此，7 _ p e ) 2 = ；， 类似地，丁白一c ) ；，最后，r ( c ) 2x + 2 ；+ = 器 如果d ( 厶：) 5 ，那么c 从所有相邻的面共获得权 另一方面，r 和一c ) 2 ；= j ，丁白一c ) j 因此，f ( c ) 2 ；+ 2 + ；= 面3 2 ( 2 4 b ) 假设3 d ( z ) s4 ，那么南扛) = 南臼) = 0 ，t r ( x ) = t ( $ ) ，f ( 们= t 白) 观察表1 ，点g 和各转移权至少；给c 因为d ( l 。) ，d ( 如) ，d ( ，如) ，d ( l 。) 5 ， 所以c 从它相邻的面总共获得权 最后有r ( c ) i 4 + 2 ；= 蠢3 2 ( z 4 0 假设d ( v ) = d ( z ) = 5 此时，d 2 ( z ) = d 2 ( ) 一d 3 ( x ) = d 3 ( y ) = 0 因此， 下 一c ) 2 i = 1 ，类似地，r 0 一c ) 1 ，最后有，r ( c ) 1 + 1 = 2 ( 2 4 d ) 假设d ( z ) = 5 ，d ( v ) = 6 那么d 2 ( x ) = 也( ) = 0 ，d 3 扛) ，d 3 ( y ) 1 ，推出 r 0 一c ) 2 斋= 2 ，r ( 一c ) 类似前面可证，c 从它所有邻面至少获得 权：，最后有r ( c ) 22x + i 4 = 2 ( 2 4 e ) 假设d ( z ) = d ( v ) = 6 此时，r ( x c ) 2 = ，r 白一c ) 2 = ；，r 0 一c ) i 1 ，r 扣一c ) ，面丘。，厶：，知， 。各转移权至少 给c 因此， 7 r ( e ) 2x + 4x 亏1 + 2xj = 面2 3 1 4 二、平面图的边染色 情况3c 是3 - 丛，即c 就是c 3 此时，k = 3 ，d ( u ) = 3 ，不失一般性，假设d ( x ) 5 ，d ( y ) = d ( z ) = 6 显然， d 2 0 ) = d 2 0 ) = d 2 ( z ) = o 类似前面的讨论，厶。厶：，厶。都是5 + 面，每个面给c 转移权至少 对d ( x ) 进行讨论： 3 1d 0 ) = 5 此时，c 即为c 驴) 因为d ( = 3 ，d ) = 5 ，所以d 3 ( y ) = d 3 ( z ) = 1 由 ( r 1 3 ) ，点y 和z 各转移权磊4 4 给c 另外，由表2 ，7 0 一c ) 2x3 = 3 最后有 丁( c ) 2x 丽4 4 + 3 + ；= 3 3 2 d ( o ) ；6 此时，c 即为c 兽b ) 由引理2 3 ，z ，y ，z 中至少有一个点相邻一个3 - 点和五个 5 + 点不妨令口就是这样的点，那么d a ( x ) = l ，d 4 ( x ) = 0 ：由( r 1 2 ) ，茹给c 转移 权谣1 6 如果d a ( y ) = 1 ，d 4 ( ) = o ，那么根据规则( r 1 2 ) ，我们也有f 白一c ) = 丽1 6 否则，根据表l ，r 白一c ) 2 ；= ；综上分析，r 白一c ) m - - r - 1 丽t 6 ，； = ；类 似地，我们有t 0 一c ) 之因此，r ( c ) 丽1 6 十2 ；+ 3 = 3 定理2 1 得证， 下面我们给出a = 5 ，平面图是第一类的一个充分条件 首先由引理2 1 ，当g 是一个5 - | f 缶界图时，下面结论 1 ) 一( p 4 ) 显然成立 ( p 1 ) 如果d = 2 ，那么u 相邻两个5 一点 ( p 2 ) 如果d ( 口) = 3 ，那么 只能相邻4 + 点；且若d 4 0 ) 芝l ，则如( 口) 2 ( p 3 ) 如果d ( u ) = 4 ，那么u 只能相邻3 + 一点；且若d 3 0 ) = 1 ，则如( u ) = 3 ；若 也( u ) 1 ，则d 5 ( ) 2 ， ( p 4 ) 假设d ( 口) = 5 若如( u ) = l ，则d 5 ( u ) = 4 ；若d a ( v ) 1 ，则d 5 ( u ) 3 ；若 d 4 ( 口) 1 ，则d 5 ( u ) 2 定理2 2 最大度为5 且不含相交三角形的简单平面图g 是第一类 证明： 假设定理2 2 不成立，g 是第二类图不失一般性，我们可以假设g 是5 - 临 界简单平面图那么显然g 是2 连通的因此g 的每一个面的边界是一个圈，且 每一条边位于两个不同面的边界上 一1 5 一 二、平面瞄的边染色 利用前面经过改写的e u l e r 公式 ( d ( ) 4 ) + ( d ( ，) 一4 ) = 一8 , e v ( a )f e f , ( g ) 类似地，对任意$ v ( a ) uf ( g ) ，定义权函数叫 ) = d 0 ) 一4 于是g 的 所有顶点和面的权和为一8 我们将重新分配这些权使得总和不变，但是每个 z v ( a ) uf ( g ) ，有新权 0 3 ) 20 于是得到一个类似的矛盾 定义权转移规则如下： ( r 1 ) 对于每个5 - 点 ，分下面五个步骤转移权函数： ( 1 1 1 ) 给相邻的2 一点转移权l ，给相邻的3 一点转移权； ( r 1 2 ) 如果d 4 ( v ) 2 ，或者d 3 ( 口) = d 4 ( 口) = 1 ，那么 给每个相邻的4 点转移 权； ( r 1 3 ) 如果南( u ) = 0 ，反( u ) = 1 ，那么t ，给每个相邻的4 一点转移权女； ( r 1 4 ) 当( r 1 1 ) 一( r 1 3 ) 执行完毕后，如果u 关联一个3 面，那么 的剩余权转给 这个3 面 在( r 1 ) 执行完毕后，令d 0 ) 表示4 点u 获得的权，我们再执行下面的权转移规 则： ( r 2 ) 每个4 - 点给相邻的3 - 点转移权 ，。( 口) 一j 如( u ) 给关联的3 - 面 ( r 3 ) 如果一个5 + 面，相邻一个( 2 ，5 ，5 ) 一面，满足i e ( ，) n e ( f ) l = 2 ，那么，给 ，转移权1 根据规则( r 1 2 ) 和( r 1 3 ) ，我们有下面断言： 断言3 每个5 - 点转移权给相邻4 点至少； 假设 y ( g ) ，那么d p ) 2 如果d 0 ) = 2 ，那么w ( v ) = 一2 ，由( p 1 ) ，口相 邻两个5 一点由( r 1 1 ) ，叫( ) = 一2 + 1x2 = 0 如果d ( v ) = 3 ，那么 ( u ) = 一1 由( p 2 ) ，u 相邻三个4 + 点由( r 1 1 ) 和( r 2 ) ， 0 9 。如) = 一i + 3 = 0 假设d ( v ) = 4 如果口不相邻3 - 点，那么由o ( ) 0 ，易见w ( ) 0 如果口 相邻一个3 - 点，根据( p 3 ) ，可知d 5 ( u ) = 3 由断言3 ，n ( ) 3 3 = i 1 ，根据( r 2 ) ， 推出w ( u ) 0 一1 6 一 二、平面圈的边染色 假设d ( v ) = 5 令卢( u ) 表示( r 1 1 ) 一r ( 1 3 ) 执行后，点口剩余的权易见，口相邻 至多一个2 一点 如果如0 ) = 1 ，那么根据伊1 ) ，如( 口) = 4 ，由规则( r 1 1 x 可知盆( 口) = 0 ，再根 据规则( r 1 4 ) ，t i ( u ) = 0 于是假设d 2 ( ) = 0 由( p 2 ) ，显然有d 3 ( ) s2 如果如( u ) = 2 ，则d 4 ( v ) = 0 ，因此由( r 1 1 ) 有 p ( ) 2l 一 2 = 如果d 3 扣) = 1