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

摘要 平面图的点染色 摘要 图g 的一个正常顶点染色是指 种颜色1 ，2 ，忌对于g 的各顶点 的一个分配，使得任意两个相邻的顶点分配以不同颜色，若图g 有一 个正常k 点染色，那么就称图g 是k 点可染色的图g 的色数是指g 有 一个正常七顶点染色的数k 的最小值，用x ( g ) 表示 图g 的一个顶点色列表工是一个颜色集合簇，它指定g 的每个顶 点口一个颜色集合l ( ) 若g 有一个正常的顶点染色7 r ，使得对每一个 顶点口v 。有7 r ( u ) l ( ) ，则称g 为l 。顶点可染的或者称订是g 的一 个l 染色若对每一个满足i l ( 掣) i k ，即v 的厶g 都是l 点可染的， 则称g 是而点可选择的，简称g 是k 可选择的g 的顶点列表色数是使 得g 是后可选择的最小的非负整数后 假若染色玎是图g 的正常顶点染色，并且对于g 中的任何一个圈 子图a 都应用至少3 种颜色，那么我们称染色7 r 是g 的一个无圈染色 图g 的无圈色数尬( g ) 就是使得g 是无圈七可染的最小的非负整数忌 若g 有一个正常的无圈染色丌，使得对每一个顶点甜v ，都有7 r ) 三( t ，) ，则称g 是无圈三可染的或者称7 r 是g 的一个无圈己染色若对满 足i l ( v ) l k ，可v 的色列表厶g 都是无圈l 可染的，那么称g 是无 圈惫可选择的g 的无圈列表色数x ：( g ) 是使得g 是无圈忌可选择的最 小的非负整数惫 1 9 7 6 年，对于平面图的正常顶点着色，s t e i n b e r g 【j 】提出猜想：每个 不包含4 一圈和5 圈的平面图是3 可染色的 2 0 0 2 年，b o r o d i n 等人首次研究了平面图的无圈三染色问题，并且 在文献【2 】中证明了每个平面图都是无圈7 可选择的与此同时，他们 还在此文献中提出了一个更具有挑战性的猜想：每个平面图都是无 圈5 可选择的 摘要 本学位论文主要围绕这两个猜想，对一些平面图类展开研究 在第一章中，我们给出本文所用到的基本概念，简述了相关领域 的研究现状以及呈现了本文的主要结果 在第二章中，我们证明了以下两个结果： ( 1 ) 每个不包含 4 ，6 ，7 ，9 】圈的平面图是3 可染色的； ( 2 ) 每个不包含 4 ，6 ，8 ) 圈的平面图是3 可染色的 在第三章中，我们获得了以下两个结果： ( 1 ) 每个不包含4 一圈的平面图是无圈6 可选择的； ( 2 ) 每个不包含4 圈并且任意两个三角形之间的距离至少是3 的平 面图是无圈5 可选择的 关键词：平面图，点色数，选择数，无圈染色，圈 a b s t r a c t v e r t e xc o l o r i n go fp l a n a rg r a p h s a b s t r a c t a p r o p e rk - c o l o r i n go fg i sa l la s s i g n m e n to f 七c o l o r sl ，2 ，ks u c h t h a tn oa d j a c e n tv e r t i c e sr e c e i v et h es a m ec o l o r i fgh a sap r o p e r 七一 c o l o r i n g ，t h e ng i ss a i dt ob ek - c o l o r a b l e 。t h ec h r o m a t i cn u m b e r , d e n o t e d b yx ( g ) ，i st h el e a s tn o n - n e g a t i v ei n t e g e rks u c ht h a tg i sk - c o l o r a b l e w e s a yt h a tli s 锄a s s i g n m e n tf o rt h eg r a p hg i fi ta s s i g n sal i s tl ( v 1 o fp o s s i b l ec o l o r st oe a c hv e r t e xvo fg i fgh a sap r o p e rc o l o r i n g7 rs u c h t h a t7 r ( v ) i ( v ) f o ra l lv e r t i c e s 移，t h e nw es a yt h a tgi sl c o l o r a b l eo r7 r i sa l l 三一c o l o r i n go fg t h eg r a p hgi sk - c h o o s a b l ei fi ti s 五一c o l o r a h l ef o r e v e r ya s s i g n m e n tls a t i s f y i n gi l ( 口) l kf o ra l lv e r t i c e s 可t h el i s tc h r o - m a t i cn u m b e ro fg ，i st h es m a l l e s ti n t e g e r 局s u c ht h a tgi sk - c h o o s a b l e a p r o p e rv e r t e xc o l o r i n g 丌o fag r a p hg = ( ue ) i sa c y c l i ci fg c o n - t a i n sn ob i c o l o r e dc y c l e t h ea c y c l i cc h r o m a t i cn u m b e r , d e n o t e db yx o ( a ) ， o fa g r a p hgi st h el e a s ti n t e g e r s u c ht h a tg h a sa na c y c l i ck - c o l o r i n g a g r a p hgi sa c y c l i c a l l yl l i s tc o l o r a b l ei ff o rag i v e nl i s ta s s i g n m e n tl t h e r ei sa na c y c l i cc o l o r i n g 丌o ft h ev e r t i c e ss u c ht h a t7 r ( v ) l ( 口) i fgi s a c y c l i c a l l yl - l i s tc o l o r a b l ef o ra n yl i s ta s s i g n m e n tw i t hi l 扣) i 后f o ra l l 口v ( g ) ，t h e ng i sa c y c l i c a u yk - c h o o s a b l e t h ea c y c l i cl i s tc h r o m a t i c n u m b e r , d e n o t e db y 砭( g ) ，o fa g r a p hg i st h es m a l l e s ti n t e g e r 惫s u c ht h a t gi sa c y c l i c a l l yk - c h o o s a b l e i n1 9 7 6 ，s t e i n b e r gu l c o n j e c t u r e dt h a te v e r yp l a n a rg r a p hw i t h o u t4 - c y c l e sa n d5 一c y c l e si s3 - c o l o r a b l e i n2 0 0 2 ，b o r o d i nc ta 1 嘲f i r s ti n v e s t i g a t e dt h ea c y c l i c a l l yl i s tc o l o r i n g o f p l a n a rg r a p h st op r o v et h a te v e r yp l a n a rg r a p hi sa c y c l i c a l l y7 - c h o o s a b l e t h e ya l s op u tf o r w a r dt ot h ef o l l o w i n gc h a l l e n g i n gc o n j e c t u r e ：e v e r yp l a - n a f g r a p hi sa c y c l i c a u y5 - c h o o s a b l e 一i 一 a b s t r a c t i nt h i sm a s t e rt h e s i s ，w ea i ma tt h ea b o v et w oc o n j e c t u r e s ，a n di n v e s t i g a t es o m ec o l o r i n gp r o b l e mo fp l a n a rg r a p h s i nc h a p t e r1 ，w ec o l l e c ts o m eb a s i cn o t i o n su s e di nt h et h e s i sa n d g i v e ac h i e f s u r v e yi nt h i sd i r e c t i o n m a i nr e s u l t si nt h et h e s i sa r es t a t e d i nc h a p t e r2 ，w ep r o v et h a t ： ( 1 ) e a c hp l a n a rg r a p hw i t h o u t 4 ，6 ，7 ，9 ) 一c y c l e si s3 - c o l o r a b l e ； ( 2 ) e a c hp l a n a rg r a p hw i t h o u t 4 ，6 ，8 ) 一c y c l e si s3 - c o l o r a b l e i nc h a p t e r3 ，w eo b t a i nt h a t ： ( 1 ) e a c hp l a n a rg r a p hw i t h o u t4 - c y c l e si sa c y c l i c a l l y6 c h o o s a b l e ； ( 2 ) e a c hp l a n a rg r a p hw i t h o u t4 - c y c l e sa n dw i t h o u tt r i a n g l e sa td i s - t a n c el e s st h a n3i sa c y c l i c a l l y5 - c h o o s a b 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 cn u m b e r l i s tc h r o m a t i cn u m b e r a c y c l i cc o l o r i n g ，c y c l e i v 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果论文中除了特别加以标注和致谢的地方外。不包含其他人或其他机 构已经发表或撰写过的研究成果其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意 研究生签名；隰 学位论文使用授权声明 日期蚵f 2 竹 i 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生签名：橡 翩繇舢帆岬 | jf 4 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：讲钗 指导钏盹珊氏 一、绪论 ( 一) 、基本概念 一、绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号 一个有序对g = ( v e ) 称为一个无向图，其中v 是一个有限集合，e 是y 中的不同元素的无序对的集合y 中的元素叫做图g 的项点，e 中的元素叫做 图g 的边我们通常用y ( g ) ，e ( g ) 分别表示图g 的顶点集合与边集合，用l v ( c ) i ， l e ( c ) 1 分别表示g 的顶点数与边数没有环和重边的图叫做简单图除非特别 指出本文研究的图均指有限简单无向图，对于图g 中的顶点“和 ，若边e = 删e ( g ) ，则称t 和口相邻。t 和甜互为邻点同时也称和可是e 的辅点，n 和口分 别与e 相关联若“( 或e ) 在面，的边界上，则说“( 或e ) 与，在g 中相关联称有一 个公共端点的两条边相邻，以及至少有一条公共边的两个面相邻设是一 个顶点，与v 相关联的边的条数叫做口的度数，记作d g ( 秽) 与钌相邻的顶点的 全体叫作口在图g 中的邻域，记作0 ( a ) 度数为，至少为k ，或至多为的顶 点我们称为女一点，矿点，或女一点g 中顶点的度中最大者和最小者分别称 为g 的最大度和最小度，分别记作( g ) 和6 ( g ) 在不产生混淆的情况下，我们 把i v ( g ) i ，i e ( g ) j ，g ( 秽) ，d g ( ”) ，( g ) ，6 ( g ) 分别简记为i y i ，l e l ，( 秽) ，d c v ) ，j 图g 的一条途径是一个有限非空的点边交替序列 = v o e l v l e 2 f e k v k ，使 得对lsi ，略= 职1 y i 若途径w 上的顶点v o ，秒1 ， 0 2 ，互不相同则 称铷为一条踌，记作r ，称，分别为路晟的起点和终点称起点和终点相同 的路为圈，并且把路( 圈) 上的边数记为路( 圈) 的长度，一个3 一圈被称为三角形 假设三角形a ，为，它们之间的距离就是两个三角形中任意两点的最短距离 即d i 甜( 乃，t 2 ) = r a i n d i d = d i s t ( u 。w ) ，v “死，t 2 如果d i s t ( t x ，乃) = 0 ， 那么称三角形死和乃相交称图g 中最短圄的长度为g 的围长。记作g ( g ) 如果 图g 中的每个项点的度数都是k 的话，那么称图g 是k 正则图若对于图g 中的任 意一个子图，都存在一个k 一点，则我们称g 是一退化的 如果能将图g 画在平面上，使得它的边仅在端点处才可能相交，则称图g 是可 平面化图，图的这种平面上的画法称为图的平面嵌入。或称为平面图设图g 是平 面图，我们常用f ( g ) 表示面集合对于，( g ) ，用6 ( ，) 来表示面，的边界若，的 边界点依顺时针方向排列为钍“u 2 ，那么我们就记，= 阻1 “2 1 有时 一、绪论 简记y ( ，) = y ( 6 ( ，) ) 把途径6 ( ，) 的长度称为面，的度度数为，至少为，或至多 为k 的面，我们称为k 面，+ 面，或一面若一个面的边界是一个圈，则称这个面 是一个简单面 本文所用术语和符号基本上与文献【3 】一致文中未介绍的其他图论术语将 在必要时予以阐述 ( 二) 、关于平面图染色的研究现状 图染色问题的研究来源于著名的四色问题，即在平面上任何一张地图，总可 以用至多四种颜色给每一个国家染色，使得任何两个相邻国家( 公共边界上至少 有一段连续曲线) 的颜色是不同的关于平面图的染色问题是图论界的热点也是 难点 图g 的一个正常顶点染色是指k 种颜色1 ，2 ， 对于g 的各顶点的一个分 配，使得任意两个相邻的顶点分配以不同颜色若图g 有一个正常k 点染色，那么 就称图g 是k 点可染色的图g 的色数是指g 有一个正常k 顶点染色的数k 的最小 值，用x c c ) 表示 图g 的一个顶点色列表l 是一个颜色集合簇，它指定g 的每个顶点”一个颜色 集合l ( 口) 若g 有一个正常的顶点染色丌使得对每一个项点 v ，有7 r ( v ) l ( 移) ， 则称g 为三一顶点可染的或者称7 r 是g 的一个l 。染色若对每一个满足i l ( t ，) i k ， v v 的lg 都是l 点可染的，则称g 是k 点可选择的，简称g 是k 一可选择的g 的 顶点列表色数是使得g 是k 一可选择的最小的非负整数k 1 9 9 3 年，t h o m a s s e n 4 1 证明了每个平面图都是5 一可选择的由此，人们不禁要 闯：任何一个平面图都是4 - 可选择的吗? 答案是否定的因为v o i g t 【5 】找到了一类 平面图g ，事先给图g 中每个顶点配置4 种颜色的列表，但无论采取怎样的染色方 式，都不能使图g 正常染色接下来，人们试着对4 可选择的平面图类作一些特征 刻画l a m 等人于1 9 9 9 年证明了： 定理1 1 6 1 不包含舢圈的平面图是4 - 可选择的 两年之后，l a m 等人在文献【7 冲又证明了： 定理1 2 若平面图g 中任何两个三角形的距离至少为3 ，那么图g 是4 一可选择的 与此同时，w a n g 和l i h 也分别得到了以下三个结果： 定理1 3 嘲不包含5 圈的平面图是牟可选择的 一2 一 一、绪论 定理1 4 【9 】不包含6 一圈的平面图是4 - 可选择的 定理1 5 1 0 1 不包含相交三角形的平面图是4 可选择的 关于2 一可选择的问题，e r d 3 s 等人在文献【1 1 中已经做了特征化的论述 由此。许多学者对平面图3 ，可染( - q - 选择) 的问题做了一系列的探讨与研究 1 9 5 8 年。g r o t z s c h1 1 2 1 i 正明了不包含3 。圈的平面图是3 一可染色的v o i g t 1 3 1 进 一步指出不包含3 圈的平面图不可以是3 可选择的从平面图的围长出发， t h o m a s s e n 在文献【1 4 中证明了： 定理1 6 每个满足g ( g ) 5 的平面图g 是3 可选择的 1 9 7 6 年对于平面图的正常顶点着色问题，s t e i n b e r g 提出了以下猜想： 猜想1 1f l l 每个不包含舡圈和5 一圈的平面图是3 一可染色的 对于这个猜想，e r d i ，s 在文献【1 5 冲重新把它表述为：是否存在一个常数， 使得不包含 4 ，5 ，) 圈的平面图是3 一可染色的许多学者围绕着此猜想 做了大量的研究，a b b o t t 和z h o u1 1 6 在1 9 9 1 年得到了一个较小的上界k + = 1 1 b o r o d i n 1 7 1 。s a n d e r s 和z h a o 1 8 1 分别将k 从1 1 降低到了9 ，即假若平面图g 不包 含 4 ，5 ，9 ) 一圈，那么图g 是3 一可染色的 在2 0 0 5 年。b o r o d i n 等人又再一次把k + 从9 降到了7 ，如下： 定理1 7 i t 9 每个不包含 4 ，5 ，6 ，7 ) 一圈的平面图是3 一可染色的 从目前已知的研究现状来看，假若在平面图中去掉四类长度的圈，有下面这 些研究结果： z h a n g 和w u 在2 0 0 5 年得至3 j t ： 定理1 8 【2 0 1 每个7 f 包含 4 1 5 ，6 ，9 ) 一圈平面图是3 一可选择的 l u 和x u 把此结果改进为： 定理1 91 2 1 1 每个不包含 5 ，6 ，9 ) 一圈且无相邻三角形的平面图是3 - 可选择的 与此同时，w a n g 和w a n g 在文献【2 2 】中证明了： 定理1 1 0 每个不包含 4 ，5 ，7 ，9 ) 一圈的平面图是3 一可选择的 2 0 0 6 年，w a n g 和c h e n 2 3 1 ，c h e n ，r a s p a u d 年1 w a n gu a ，l u o ，c h e n 8 1 w a n g 2 5 1 ， 及c h e r t 和w a n g 郾】分别得到了以下四个结果： 一3 一 一、绪论 定理1 1 1 每个不包含 4 ，5 ，6 ，8 ) 一圈的平面图是3 一可染色的 定理1 1 2 每个不包含 4 ，6 ，7 ，9 ) 一圈的平面图是3 一可染色的 定理1 1 3 每个不包含 4 ，6 ，7 ，8 ) 一圈的平面图是3 一可染色的 定理1 1 4 每个不包含 4 ，6 ，7 ) 一圈以及相邻5 一圈的平面图是3 一可染色的 之后的一年，s h e n 和w a n g 在文献【2 7 仲给出了： 定理1 t 5 每个不包含 4 ，6 ，8 ，9 ) 一圈的平面图是3 一可选择的 下面再来介绍一下在平面图中去掉三类长度圈的研究现状： 2 0 0 6 年，x u 在文献【2 8 中证明了： 定理1 1 6 每个不包含 5 ，7 一圈且无相邻三角形的平面图是3 一可染色的 上述结果蕴涵了： 推论1 1 每个不包含 4 ，5 ，7 ) 圈的平面图是3 一可染色的 与此同时，w a n g 和c h e n 证明了： 定理1 1 71 2 9 1 每个不包含 4 ，6 ，8 ) 一圈的平面图是3 一可染色的 此外。m o n t a s s i e r , r a s p a u d _ 平 j w a n g ：e 平面图中去掉某些短圈的基础上再加以 限制三角形之间的距离他们在文献【3 0 q ，得到了以下三个结果： 定理1 1 8 每个不包含 4 ，5 一圈并且任意两个三角形的距离至少是a m 平面图 是3 一可选择的 定理1 1 9 每个不包含 4 ，5 ，6 ) 一圈并且任意两个三角形的距离至少是3 的平面图 是3 一可选择的 定理1 2 0 存在一个不包含 4 ，5 ) 圈并且不包含相交三角形的平面图是非3 一可选 择的 倘若仅仅考虑去掉5 圈的平面图并且对图中的三角形之间的距离加以限制， b o r o d i n 和r a s p a u d 在文献 3l 】中证明了下面这个结果： 定理1 2 1 每个不包含5 圈并且任意两个三角形的距离至少是4 的平面图是3 一可 染的 一4 一 一、绪论 以上是关于平面图3 染色以及3 一选择的一些已知结果与研究现状接下来， 我们再来介绍一下平面图无圈染色以及无圈列表染色的相关结果以及研究进展， 假若染色7 r 是图g 的正常顶点染色，并且对于g 中的任何一个圈子图g 都应用 至少3 种颜色，那么我们称染色7 r 是g 的一个无圈染色图g 的无圈色数( g ) 就是 使得g 是无圈 可染的最小的非负整数若g 有一个正常的无圈染色7 r ，使得对 每一个顶点口v ，都有7 r ( 口) l ( 剖) ，则称g 是无圈己可染的或者称丌是g 的一个 无圈l 染色若对满足i l ( 口) l ， 1 3 v 的色列表厶g 都是无圈l 可染的，那么 称g 是无圈可选择的g 的无圈列表色数砭( g ) 是使得g 是无圈k 可选择的最小 的非负整数k g r i i n b a u m 在文献【3 2 中首次提到了图的无圈染色概念，并给出了下面这个 猜想： 猜想1 21 3 2 1 每个平面图都是无圈5 一可染色的 围绕着这个猜想，m i t c h e m l 3 3 1 ，a l b c r t s o n 和b e r m a n ，k o s t o c h k a1 3 5 1 都做了 大量的研究工作。1 9 7 3 年，g r i i n b a u m 3 2 1 最先找到了一类4 正则的平面图满 足( g ) = 5 三年之后，k o s t o c h k a 和m e l n i k o v 嘶1 也构造了一类平面2 可退化 二部图是非无圈年可染色的这就表明g r i i n b a u m 的猜想的上界是最小的1 9 7 4 年， m i t c h e m 在文献【3 3 中证明了： 定理1 2 2 每个平面图都是无圈8 _ 可染色的 1 9 7 7 年，a l b e n s o n 和b e r m a n 将m i t c h e m 的结果进一步改进为： 定理1 2 31 3 7 1 每个平面图都是无圈7 可染色的 k o s t o c h k a 又得到了更接近猜想的结论，即： 定理1 2 41 3 5 1 每个平面图都是无圈6 一可染色的 1 9 7 9 年，b o r o d i n 【3 8 】成功地完成了g r i i n b a u m 猜想的证昵 1 9 9 9 年，b o r o d i n ，k o s t o c h k a 和w o o d a l l 3 9 1 尝试着对平面图的围长加以限制， 得到了以下两个结果： 定理1 2 5 每个满足g ( a ) 7 的平面图是无圈3 可染色的 定理1 2 6 每个满足g ( c ) 5 的平面图是无圈4 _ 可染色的 此外，文献 4 0 i q ，提到了每个1 平面图都是无圈2 0 一可染色的所谓l 一平面图 就是每条边最多和一条边相交的平面图 一5 一 一、绪论 2 0 0 2 年，b o r o d i n 等人首次对平面图的无圈列表染色做了一系列的研究工作 在文献【2 】中，他们证明了： 定理1 2 7 每个平面图都是无圈7 一可选择的 与此同时他们还提出了一个更具有挑战性的猜想： 猜想1 3 【2 j 每个平面图都是无圈5 一可选择的 为了方便叙述，我们先来定义一下图g 的最大平均度m a d ( g ) ，即m a d ( a ) = m a x 2 1 e ( h ) j v ( h ) i ，日g ) 2 0 0 6 年，m o n t a s s i e r , o c h e m 和r a s p a u d 】从图g 的最大平均度的角度出发，得 到了相应较好的结果，即： 定理1 2 8 每个满足m a d ( a ) ；的平面图是无圈3 可选择的 定理1 2 9 每个满足m a d ( v ) 2 ，那么 从规则( r 1 ) 至限3 ) 可知，不给点z 2 权数因此，容易发现 7 ( ，) 1 0 7 1 4 = o 2 否则，我们有d ( z 2 ) = 4 ，m 5 ( z 2 ) = 2 ，并且z 2 不和3 一面相关联因此，结合( r 3 3 ) ，我 们可知道，给点。2 的权数是0 2 于是，我们得到 ( ，) 1 0 7 1 4 一o 2 = 0 ， 假设i 4 ( ，) i = 6 容易推导得到，至少和七个5 一面相邻，因此，存在一个不 同于z 2 的点。“它从，处最多拿1 1 如果d ( 。2 ) 5 ，那么由断言3 可以知道，给勋最 多 因此，我们有叫7 ( ，) 1 0 6 1 , 4 1 1 一；= 现在我们可假设d ( ：c 2 ) = 4 因 为 和，2 中至少有一个面是5 一面，所以从断言1 可以看出。2 不和3 一面相关联因此， 结合规贝u ( n 3 3 ) ，给0 2 权数最多为0 5 由此，埘7 ( ，) 1 0 6 1 4 1 1 0 5 = 0 假设l 4 ( ，) l = 5 ，那么，存在不同于。2 的两个点使得其每个点都从面，处最 多拿1 1 如果d ( z 2 ) 5 ，结合断言3 ，我们有铷( ，) 1 0 - 5 1 4 2 1 ，1 一 = 舌 如果d ( 。2 ) = 4 ，显然断言1 保证了，l 和，2 都不是3 一面，由此得n m 3 ( x 2 ) 1 再结合 规n ( r 3 2 ) 和( r 3 3 ) ，给点茁2 最多0 8 于是，( ，) 1 0 - 5 0 8 2 x1 1 一o ，8 = 0 假设| 4 ( 删4 容易得到卸7 ( ，) 1 0 4 1 4 3x 1 1 1 = o 1 ( 4 ) 假设d ( f ) = 1 0 那z a ( i ) = 1 4 因为g 中不包含关联十个3 一点的1 0 一 圈，所以，至少关联一个4 + 。点，设为奶由此，i k 5 ( 删9 如果，至少和两 个4 + 一点相关联，那么从规n ( n 3 ) 可以看出，给这两个4 + 点的权数最多各1 因 此t ，7 ( ，) 1 4 8 1 5 2 1 = 0 如果有d ( x 2 ) 5 或者d ( x 2 ) = 4 且m 3 ( 。2 ) = 0 ， 那么，对照规则( r 3 3 ) 以及断言3 马上可以得到叫( ，) 1 4 9 1 5 0 5 = 0 此 时就剩下一种情况，即对任意i 2 ，d ( z ；) = 3 且d ( z 2 ) = 4 ，其中2 ：2 至少和一个3 一面 相关联 假设i 5 ( 删= 9 此时b ( ，) 包含了九个3 一点并且使得每个3 一点都关联着一 个3 面，也就是说，l 和，2 中恰好有一个面是3 一面不失一般性，假设d ( ，2 ) = 3 因 为a ( s ) = 1 0 ，所以结合规则( r 3 2 ) - i 断定，给点$ 2 的权数是0 5 因此结合之前的讨 论，我们可以得到铷( ，) 0 假设l h 5 ( ，) l = 8 同样地，6 ( ，) 包含了一个不同于z 2 的点奶对照规n ( r 4 ) 发 现从，处最多拿1 4 根据定义，孔不和3 - 面相关联，也就是说d ( 一1 ) 3 1 t d ( ) 3 我们考虑接下来的两种子情况： ( i ) 若i 1 ，3 ，则有。“。2 以及z i + 1 善2 我们可以断言 和 一l 的度数都 超过5 因此结合( r 4 2 ) 口- i 知，给q 的权数是1 ，并且有 ( ，) 1 4 82 1 1 = 0 一1 2 一 二、关于平面陶3 染色问题 事实上，如果d ( ) = 5 ，那么根据断言1 ，我们同样可以知道 + l 不是3 一面因此 有m 3 ( x i + 1 ) = 0 这将与2 7 t + l k 5 ( ，) 相矛盾如果d ( 五一1 ) = 5 ，类似的矛盾将同 样可以得到 ( i i ) 若j = 1 或者3 ，不失一般性，设i = 3 令，7 是与z 2 相关联的并且不同 于 ，丘以及，的面因为铂5 ( ，) ，所以2 ：4 和3 面相关联这暗示着d ( ) = 3 断言1 蕴涵t d ( 知) 5 如果d ( s 2 ) 5 ，那么类似于上述讨论，我们可知m 5 ( z 3 ) = o 以及 ( ，) 0 。如果d ( ，2 ) = 5 ，那么断言1 仍然蕴涵着，7 不是3 面当d ( f 1 ) 3 时