（运筹学与控制论专业论文）平面图3可着色的充分条件.pdf

摘要 摘要 1 9 7 6 年，s t e i n b e r g 猜想每个既不含4 一圈也不含5 一圈的平面图是3 一可着 色的之后，e r d 6 s 提出一个较s m i n b e r g 猜想稍弱的问题：是否存在整数k ，使得 每个不含4 至k 圈的平面图是3 一可着色的 本篇论文证明了平面图的3 着色的三个充分条件，即： 1 每一个不含4 至6 圈，也不含距离小于2 的三角形对，且每个7 一圈 最多与一个三面相邻的平面图是3 一可着色的； 2 每一个不含4 一圈和5 一圈，且每个6 一圈或7 一圈不与长度小于8 的圈有公共边的平面图是3 一可着色的； 3 每一个不含5 圈，且每个4 一圈，6 一圈或7 一圈不与长度小于8 的圈 有公共边的平面图是3 一可着色的 论文的最后，我们还提出了进一步可探讨问题 关键词：平面图；圈；着色； a b s t r a e t a b s t r a c t i n19 7 6 ，s t e i n b e r gc o n j e c t u r e dt h a te a c hp l a n a rg r a p hw i t hn e i t h e r4 - n o r 5 - c y c l e s i s3 - c o l o r a b l e e r d 6 ss u g g e s t e dt h ef o l l o w i n gr e l a x a t i o no ft h i sp r o b l e m ：d o e st h e r e e x i s tac o n s t a n t 七s u c ht h a tt h ea b s e n c eo fc y c l e sw i t hs i z ef r o m4t o 七i nap l a n a r g r a p hg u a r a n t e e si t s3 - c o l o r a b i l i t y ? i nt h i sp a p e r , w ew i l lp r o v et h ef o l l o w i n gs u f f i c i e n tc o n d i d o n so n3 - c o l o r a b l e p l a n eg r a p h s ： ( 1 ) l e tg b eap l a n eg r a p hw i t hn e i t h e rc y c l e so f l e n g t hf r o m4 t o6n o rt r i a n g l e s o fd i s t a n c el e s st h a nt w o f u r t h e r m o r e ，i fe v e r y7 - c y c l e so fgi sa d j a c e n tt oa tm o s t o n et r i a n g l e ，t h e ngi s3 - c o l o r a b l e ( 2 ) e v e r yp l a n eg r a p h 丽t hn e i t h e rc y c l e so fl e n g t h4 ，5n o rc y c l e so fl e n g t h6 a n d7a d j a c e n tt oc y c l e so f l e n g t hl e s st h a n8i s3 - c o l o r a b l e ； ( 3 ) e v e r yp l a n eg r a p hw i t h o u t5 - c y c l e so fw h i c he a c h4 , 6o r7 - c y c l ei sn o ta d j a - c e n tt oc y c l e so fl e n g t hl e s st h a n8i s3 - c o l o r a b l e w ew i l la l s ob r i n gf o r w a r ds o m eq u e s t i o n st h a tn e e dt ob ef u r t h e ri n v e s t i g a t e d k e y w o r d sp l a n eg r a p h ；c y c l e ；c o l o r i n g 一一 前言 - 厶- j - _ _ 刖吾 1 7 3 6 年，瑞士数学家欧拉在他的一篇论文中讨论了哥尼斯堡七桥问题， 由此诞生了一个全新的数学分支一图论。在经历了2 0 0 多年的发展之后，图论 由最初主要用来讨论游戏中遇到的问题到现在用来解决生产管理、军事、交 通运输、计算机以及通信网络等领域中的许多离散问题，其理论和结果越来 越丰富，在其他学科领域越来越受到人们的重视。 在图论的许多著名问题中，最著名也最难以证明的问题之一就是地图的 着色问题。 1 8 5 2 年，德摩根的一个学生g u t h r i e 提出，可以用四种颜色给地图上的 各个国家着色，且使得各个相邻的国家所着上的颜色不同。德摩根对此问 题极其感兴趣，并向数学界公布了此问题。这就是著名的四色问题。后来， 四色问题曾一度被列为与数论中的f e r m a t 猜想，函数论中的r i e m a n n 假设相 提并论的三大数学难题之一，受到世界上许多最有才华的数学家的冲击。历 史上曾有许多人宣布证明了它，但都被后人一一否定。1 9 7 6 年，美国数学家 k e n n e t ha p p l e 和w o l f g a n gh a k e n 宣布了一个借助于计算机的证明。但是， 这个证明引起了广泛的争论，原因是在他们的证明中使用了超过1 0 0 0 h 的机 时，它是不是真的证明四色问题? 实际上，如果我们把一个国家做为一个点，而国家与国家相邻视为点与 点之间有边，那么，四色问题，就可以看成是平面图的着色问题了。 平面图的着色问题是许多图论学者讨论过的问题，涉及到点着色，边着 色，全着色等等。图的点着色问题在图着色理论中占有最基础、也最重要的 地位，有非常丰富的研究成果，也还存在着很多重要的未解决的问题。平面 图的四着色问题解决后，人们开始关注平面图的三着色问题。本文主要讨论 的就是平面图的三着色的几个充分条件。 第1 章基本概念和已有结论 第1 章基本概念和已有结论 定义1 0 1 图g 是一个三元组，这个三元组包含一个顶点集y ( g ) ，一个边集 e ( g ) 和一个关系，该关系使得每一条边和两个项点( 不一定是不同的点) 相 关联，并将这两个顶点称为这条边的端点 我们所研究的图为有限简单图除特别声明，我们所使用的符号，概念都 与【6 】中一致 定义1 0 2 设g = ( y ( g ) ，e ( g ) ) 是图，v 是g 的顶点，称d a ( v ) 和g ( u ) 分别 是v 的点度和邻域g 的最小度记为6 ( g ) 定义1 0 3 设u ：v ( a ) 叶 1 ，2 ，克) 是从g 的顶点集y 到整数集的一个 映射，如果对于任意的删e ( g ) ，有c ( 让) c ) ，那么我们称c 是g 的一个 南一正常着色而使得g 存在正常着色的最小的整数k 称为g 的着色数，记作 x ( g ) 同时，g 中的点u 所着的颜色记为c ( u ) 定义1 0 4 对g 中的每个顶点 ，给定一个颜色的集合二，记为三( u ) ，若对任意给 定的三( 口) ，都存在g 的一个正常着色，使得对任意的顶点v 都有c ( v ) 三( ) ， 则称e 是g 的一个三列表染色给定正整数k ，及任意事先给定的颜色列表 l = l ( v ) l v y ( g ) ) ，如果l l ( ) i k 对每一个顶点u 都成立，g 总有一个 兀列表染色，则称g 是克列表可染色的。使得g 有后列表染色的最小正整数 k ，称为g 的选色数，记为x t ( a ) 显然，x ( a ) x s ( a ) 定义1 0 5 设g 是平面图记p ( a ) 为g 中面的集合若，f ( g ) ，的边界 的所包含的边数记为d ( t 厂) ，其中割边计两次；边界所包含的点记为y ( 厂) 若 u y ( ，) ，则称v 与，相邻若两个面 ，如有公共边，则称，1 与，2 相邻 定义1 o 6 设u 是图g 的顶点，如果d ( v ) - - - 七或d ( u ) k ，则称v 是一个k 度 点或k + 度点类似的称s f ( s ) 是一个k 度面或k + 度面如果d ( f ) = k 或 d ( s ) k 一2 一 第l 章基本概念和已有结论 定义1 o 7 对于平面图g 中的圈g ，用i n t ( c ) 表示位于圈c 中的点集；用 f 疵( c ) 表示位于圈外的点集若l 佗t ( c ) 0 且e 戚( c ) 毋，则称圈c 为分离 圈 定义1 o 8 设c f 0 ) = 3 且 是一个与三角形相邻的内部点，则称 为坏点 图的点着色研究曾一度成为了图论学者研究的热点，从四色问题的提 出，到著名的五色定理，最后学者们把点着色的研究重点放在的平面图 的3 一着色上面，出现了很多猜想，得到了很多的结论，并且逐步改进了结 论。关于平面图可3 着色，我们列出部分已知的结论： 定理1 o 1 ( 【5 】) 每个不含3 一圈的平面图是3 一可着色的 定理1 o 2 ( 【6 】) 每个不含4 至1 1 圈的平面图是3 一可着色的 定理1 0 3 ( 【2 】) 每个不含4 至7 圈的平面图是3 一可着色的 定理1 0 4 ( 【8 】) 每个既不含5 一圈也不含7 一圈，且不含相邻3 一圈的平面图 是3 一可着色的 - 3 一 第2 章 平面图3 可着色的三个充分条件 第2 章平面图3 可着色的三个充分条件 设r 1 是不含垂6 圈，也不含距离小于2 的三角形对，且每个7 一圈最多 与一个三面相邻的平面图集合；f 2 是不含4 一圈和5 圈，且每个6 _ 圈或7 一圈不与 长度小于8 的圈有公共边的平面图集合1 1 3 是不含5 圈，且每个禾圈，昏圈或7 圈 不与长度小于8 的圈有公共边的平面图集合 在本章中，我们将证明如下定理： 定理2 0 5 v g i 1 ，x ( g ) 3 定理2 o 6 y g f 2 ，x ( v ) 3 定理2 0 7 v g f a ，x ( g ) 3 2 1 定理2 0 5 的证明 为了证明上述结论，我们给出如下的结构引理： 引理2 1 1 v g f 1 ，6 ( g ) 2 证明假设结论不成立，即对于图g f 1 6 3 我们给g 中的项点和面赋一 个初始的权重w 其中对每个顶点叫( u ) = 2 d ( v ) 一6 ；每个面w ( f ) = d ( ) 一6 由e u l e r 公式l y ( g ) f l e ( g ) i + f f ( g ) l = 2 ，于是有 删( z ) = ( 2 d ( ) - 6 ) + ( d ( ，) 一6 ) = - 1 2 x e v u fv e v l e f 如果我们经过一系列点和面的权重的相互调整，得到一个新的权重w + ( z ) ， z vuf ，那么必然还有伽+ ( z ) = - 1 2 而此时如果同时能保证对任意的 z vuf ，有w 。( z ) 0 ，那么我们将得到矛盾 权重的调整将依照以下的规则： 一4 一 第2 章平面图3 町着色的三个充分条件 ( r ) 每个7 + 一面转移1 给相邻的3 面 注意至0 艿( t ，) 3 ，伽+ ( ) = 2 d ( v ) 一6 0 令，是g 的一个七一面由于g 不含4 _ 6 圈，忌4 ，5 ，6 如果七= 3 ，由r ，叫( ，) 3 6 + 3 1 0 如果七= 7 ，由图g 的选择，每个7 面至多与一个3 一面相邻，由r ，w + ( ，) 7 6 1 1 0 如果忌8 ，由于g 不含距离小于2 的三角形对，至多与【鲁j 个3 一面相邻， 1 w 。( u ) k 一6 一【昙j i 0 至此，对于任意的z vuf ，都有矿( 茁) 0 于是 0 伽( z ) = 伽( z ) = - 1 2-_j_-_ z v u f z v u f 矛盾，结论得证 定理2 1 1 v g r 1 ，x f ( g ) 3 证明反证法假设g 是顶点最少的反例，即对于讹g ，存在一个列表l l ( u ) l = 3 ，使得g 不是l 一可着色的，但是对于g 的任何子图阿满足l l l g l 均成 立则g 连通，否则考虑其连通分支即可由引理2 1 1 ，对于v g r 1 ，6 ( g ) 2 设 是g 的2 一一点，由g 的最小性，h = g 是l 一可着色的，则v 总是可以 得到和其邻点不同的颜色，从而将h 的l 一着色扩充到一个g 的l 一着色矛 盾。 推论2 1 1 v g r 1 ，x ( a ) 3 2 2 定理2 0 6 的证明- - c j - h = j l 呵】 在这一节中，我们证明如下结论： 定理2 2 1 设g r 2 ，则g 的每一个长为6 至11 的圈的3 一正常着色妒都可扩充 到g 一5 一 第2 章平面图3 可着色的三个充分条件 证明设g 是边数和点数之和i ( e ( g ) i + l y ( g ) l = o ( v ) 最少的一个极小反例， 即：g 不含4 _ 圈和5 圈，且每个每圈或7 圈不与长度小于8 的圈有公共边，存 在g 中的某一个长为6 至1 1 圈局的边界d 的导出子图的3 - 着色妒不可扩充到 整个图g 引理2 2 1 g 中不可能含有长度1 1 的分离圈s 证明设g 存在着长度1 1 的分离圈s 则由g 的极小性，可把d 的正常着 色妒扩充到g j 疵( s ) ，再把得到的s 的3 一着色扩充到g e x t ( s ) 从而得到整个 g 的3 着色矛盾 引理2 2 2 g 中圈长为长为6 至8 的圈不含有弦，圈长为9 至1 1 的圈不含有非三 角形的弦 证明由于g 不含4 _ 圈和5 圈，且每个6 圈或7 圈不与长度小于8 的圈有公共边， 所以g 中圈长为6 至8 的圈不含有弦若g 中圈长为9 至1 l 的圈含有非三角形 的弦，则g 中一定含私圈或5 圈，或者存在某个每圈或7 - 圈与长度小于8 的圈 有公共边，也与g 的选取矛盾 引理2 2 3 d 是一个简单圈，无弦 证明若d 不是简单圈，则上) 一定由两个长7 的圈相交形成，则g 或者含有 了4 一圈，或者含有了5 圈，或者存在了某个6 圈或7 圈与长度小于8 的圈有了公 共边，与g 的选取矛盾 下证d 无弦，由引理2 2 2 ，若d 有弦，则9 i d l 1 1 ，且为三角形弦假设 t r y 是d 的三角形弦，伽勘e ( g ) ，w ? 2 曰( g ) 删去点铷，在边删间插入点w 7 ， 得到g ，显然o ( v 7 ) 。； 叫+ ( u ) =一4 + 吾一言 o ； 如果u 不与三面相关，由凰，叫( ) ：4 4 + i 4 o 若l ，不是乡 b n n 如果t ，与一个三面相关，由r 1 ，i ，要给予相关的三面妻， 而与t ，相关的面中除这个三面外必有三个非三角形的面，其中两个与三面l 相 邻，一个与三面不相邻，由r 3 ，一个面既无收获也不给予，两个面给予幻点各妄， 叫扣) = 4 4 一丢+ 丢2 o 如果u 不与三面相关，伽+ ( 郇) = 4 4 = 0 ( f ( 可) = 5 若 是内部点，由r 1 和飓，可至多给两个3 一面去，同时至多给一个 一9 一 第2 章平面图3 可着色的三个充分条件 非3 面i 1 ， j 伽+ ( 钉) 5 4 一三3 = o 若钐是外部点，由冠1 和醌， ( 口) 5 4 + 吾4 一三5 = o 以u ) 6 由兄1 和r 3 ，口至多给予以钉) 个吾， 伽+ ( u ) d ( 可) 一4 + d ( ) 丢o 引理2 2 1 0 3 + ( f o ) 0 证明由风和6 i f o l 1 1 ， w + ) = a ( f o ) + 4 一d m ) 专 0 4 u 引理2 2 1 1 v - 厂f o ，伽( 厂) 0 1 证明d ( f ) = 3 ，由r 1 ，删+ ( ，) = 3 4 + 3 丢= 0 _ ) o 设d ( ，) 8 ，若，与一个2 度点钞相邻，显然，由r 2 ， 厂给予口点嘉，且f l = j j d 相关的公共点中有两个点的度3 ，这两个点也是d 边界上2 度点形成的最 大路径的端点，且这两个点从面既不给予也不收获，设由这两个点划分的d 边 界上的另一段路径为，且最多，7 上的每个点的度都为3 ，且都与一个三角形相 邻，则w 。( ，) = d ( ，) 一4 + ( d ( ，) 一2 ) 三0 设d ( f ) = 6 或d ( f ) = 7 ，若 厂与一个2 度点u 相邻，显然，则由冗2 ，则，给予 可点昙，且厂与d 相关的公共点中有两个点的度3 ，这两个点也是d 边界上2 度 点形成的最大路径的端点，且这两个点从面，既不给予也不收获，设由这两个 点划分的d 边界上的另一段路径为p ，p 上的每个点都不可能与一个三角形 相邻，所以，给予p 上的点去我们按厂中2 度点的个数分下列情况讨论： o o1 ( 】) ，中2 度点的个数2 ，w + ( ，) = d ( 力一4 2 善一2 言0 或者 9 1 oo 伽+ ( ，) = d ( ，) 一4 1 吾一3 言0 第2 章平面图3 町着色的三个充分条件 ( 2 ) f e 2 度点的个数为3 若d ( f ) = 6 ，则令z 是，中不在d 上的点，因为 d ( z ) 3 ，6sld is1 1 ，则g 中存在长度1 1 的分离圈，或者g 含4 _ 圈，5 圈，或 者存在6 - 圈，7 圈与长度小于8 的圈有公共边，与g 的选取矛盾若d ( f ) = 7 ， 训( ，) = f j f ( ，) 一4 3 虽一2x 言0 ( 3 ) ，中2 度点的个数为4 则d ( f ) 6 ，否则，pu ( o f ) r e 成5 7 圈，与 g 的选取矛盾若d ( ，) ：7 ，加( ，) = d ( ，) 一4 4 丢一1 百i t 0 ( 4 ) 厂中2 度点的个数为5 同情况( 3 ) d ( ，) 6 ，7 故，以下总假设非外部面上没有2 度点 设d ( ，) = 6 ，由于g 中1 ) 1 j 6 面不与三面相邻，则，最多给每个点丢，则 1 o 训+ ( j r ) 6 4 6x 丢0 o 1 设d ( ，) = 7 ，由于g 中的7 面不与三面相邻，则，最多给每个点妻，则 1 o w + ( ，) 7 4 7x 丢0 设d ( f ) = 8 我们分下列情况讨论： ( 1 ) ：若，给其至少四个点最多都是i i k ，或者至少有两个点从，处既不收获 9 f ) 也不给予，则伽+ ( ，) 8 4 4 三一4 去0 或者w + ( ，) 8 4 6 昙0 ( 2 ) ：若，中有一个点口属于d ，则该点不是坏点，d ( v ) 3 若d ( v ) = 3 ，则 该点从，处既不收获也不给予，且，中与u 相邻的点中也有一个点属于d ，加上 其他的6 个点不可能都是坏点，w + ( 厂) 8 4 5 丢一2 吉0 若d ( v ) 4 ，且 不与三面相关，则该点从处既不收获也不给予，而其 他7 个点至少有两个点不是坏点，w + ( ，) 8 4 5 去一2 去0 若d ( v ) 4 ，且。与三面相关，我们分以下子情况讨论： ( 2 1 ) ：厂与三面不相邻，则，从 收获妄，而另外7 个点不可能都是坏点，则 )11 o 叫+ ( ，) 8 4 6 丢一1 言+ l 去0 ( 2 2 ) ：，与三面相邻，则点 既无收获也不给予，而另外7 个点不可能都是坏 点。若有6 个坏点，必有四个三角形与，相邻，则另一点7 1 , ，必然d ( u ) 4 ，则由 舷，则f 从2 ，收获去，则w 母( ，) 8 4 6 昙+ 1 吉0 若有5 个坏点，则另 两个点最多从，面收获言，则w + ( ，) 8 4 5 昙一2 石i k 0 若只有四个及 其以下的坏点，则硼( ，) 8 4 4x 罢一4 i i t 0 oo 第2 章平面图3 町着色的三个充分条件 ( 3 ) ：不妨设厂中的点都不属于d ，且或者有价坏点，或者有5 个坏点 若，有阶坏点，则，必然与四个三面相邻，则另两个点的度4 ，则这两个 点给予，面言，则叫。( ，) 8 4 6 三十2 去2 1 3 若厂有5 个坏点，或者，与四个三面相邻，则另三个点的度4 ，则这三 个点给予，面去，则w + ( ，) 8 4 5 昙+ 3 石, i k 0 或者f 与三个 ooo 1 三面相邻，则相关的六个点中必有一个点的度4 ，该点给予，面去，则 911 | ) t o + ( ，) 8 4 5 丢一2 言+ 1 去0 设c f ( 厂) = 9 由于厂最多可与4 个三角形相关，但由于g 无四元组， 所以不可能有连续的5 个坏点出现，则8 个公共点中必然有2 个非坏点，则 3 + ( ，) 9 4 6 吾一3x 言0 设d ( j ) = 1 0 由于j r 最多可与5 个三角形相关，但由于( 7 无四元组，所 以不可能有连续的5 个坏点出现，则1 阶公共点中必然有2 个非坏点，则 硼+ ( ，) 1 0 4 8 吾一2 丢0 设d ( f ) = 1 1 由于，最多可与5 个三角形相关，最多拥有1 卟公共点，则剩 下的一个点最多从f 面处收获丢，叫( ，) 1 1 4 1 0 丢一1 言0 uuu f ) 设d ( 厂) 1 2 最多，的每个点都从厂面处收获；， 叫( ，) d ( ，) 一4 一d ( ，) 舌9 o 根据前述几个引理，新权重之和大于零，说明极小反例g 不存在。从而 定理2 2 1 得证。 推论2 2 1 v g r 2 ，x ( g ) 3 证明设图g r 2 ，如果g 中既不含昏圈也不含7 圈，由定理1 0 3 ，图g 是3 可 着色的。若g 有6 - 圈或7 圈，由定理2 2 1 ，g 的每一个长为6 至1 1 的圈的3 一正 常着色妒都可扩充到g 2 3 定理2 0 7 的证明 我们首先证明如下结论： 第2 章平面图3 可着色的三个充分条件 定理2 31 设g r 3 ，则g 的每一个4 圈和长为6 至1 1 的圈的3 - 正常着色妒都 可扩充到g 证明设g 是边数和点数之和i ( e ( g ) i + i y ( g ) l = 盯( g ) 最少的一个极小反例， 即：g 不含5 圈，且每个4 - 圈，6 - 圈或7 圈不与长度小于8 的圈有公共边，存在g 中 的某一个4 - 圈，长为6 至1 1 的圈，0 的边界d 的导出子图的3 - 着色妒不可扩充到 整个图g 引理2 3 1 g 中不可能含有长度1 1 的分离圈s 证明设g 存在着长度1 1 的分离圈s ，则由g 的极小性，可把d 的正常着 色妒扩充到g v ，以( s ) ，再把得到的s 的3 - 着色扩充到g e 以( s ) 从而得到整个 g 的3 着色矛盾 引理2 3 2 g 中圈长为4 、6 至8 的圈不含有弦，圈长为9 至1 1 的圈不含有非三角 形的弦 证明由于g 不含5 圈，且每个4 圈，每圈或7 圈不与长度小于8 的圈有公共边，所 以g 中圈长为4 、6 至8 的圈不含有弦若g 中圈长为9 至1 1 的圈含有非三角形的 弦，则g 中一定含有5 圈，或者存在某个4 _ 圈，6 _ 圈或7 一圈与长度小于8 的圈有公 共边，也与g 的选取矛盾 引理2 3 3 d 是一个简单圈，无弦 证明若d 不是简单圈，则_ d 一定由两个长7 的圈相交形成，则g 或者含有 了5 圈，或者存在了某个4 一圈，昏圈或7 圈与长度小于8 的圈有了公共边，与 g 的选取矛盾 下证d 无弦，由引理2 - 3 2 ，若d 有弦，则9 i d l 1 1 ，且为三角形弦假设 删是d 的三角形弦，训秒f ( g ) 州f ( g ) 删去点伽，在边恫插入点伽7 ， 得到g ，显然仃( g 7 ) 。； + ( 口) = 4 4 + 丢一言 o ； 如果秒不与三面相关，由尺3 。w + ( 钉) = 4 4 + 吾 0 若u 不是外部点如果 与一个三面相关，由r 1 ， 要给予相关的三面 ，而 与勘相关的面中除这个三面外必有三个非三角形的面，其中两个与三面相邻，一 个与三面不相邻，由墙，一个面既无收获也不给予，两个面给予 点各；， 叫+ ( 口) = 4 4 一丢+ 三2 o 如果 不与三面相关，w 。( 秽) = 4 4 = 0 d ( ) = 5 若t ，是内部点，由尺：1 和， 至多给两个3 一面 ，同时至多给一个 非3 一面妄，叫( u ) 5 4 一 3 = 0 若 是外部点，由咒1 和风， 叫( ) 5 4 + 5 4 一三5 = o d ( v ) 6 由r 1 和r 3 ，至多给予d ( u ) 个去， 加( 钉) d ( ) 一4 十d 0 ) 丢0 引理2 3 1 1 w + ( f o ) 0 4 证明由f o = 4 ，w 广( f o ) = f 】 ( 1 o ) + 4 一d ( o ) 弓 0 u 引理2 3 1 2 v 厂y o ，叫+ ( ，) 0 1 证明d ( ，) = 3 ，由r 1 ，w + ( ，) = 3 4 + 3 丢= 0 u o 设d ( ，) 8 ，若厂与一个2 度点 相邻，显然，由恐，给予 点等，且，与d 相关 的公共点中有两个点的度3 ，这两个点也是，) 边界上2 度点形成的最大路 径的端点，且这两个点从面既不给予也不收获，设由这两个点划分的d 边界 上的另一段路径为p ，且最多p 上的每个点的度都为3 ，且都与一个三角形相 邻，则伽+ ( ，) = d ( ，) 一4 + ( d ( ，) 一2 ) 丢0 第2 章 平面图3 - 町着色的三个充分条件 设d ( f ) = 6 或d ( f ) = 7 ，若，与一个2 度点u 相邻，显然，钉d ，则会出现4 _ 圈 与6 - 圈或7 圈有公共边的情况，矛盾。 故，以下总假设非外部面上没有2 度点 设d ( ，) = 6 ，由于g 中的6 面不与三面相邻，则，最多给每个点吾，则 叫+ ( ，) 6 4 6 言0 设d ( ，) = 7 ，由于g 中的7 面不与三面相邻，则，最多给每个点去，则叫4 ( ，) 7 4 7x 言0 设d ( ，) = 8 我们分下列情况讨论： ( 1 ) ：若厂给其至少四个点最多都是；，或者至少有两个点从，处既不收获也 不给予，则 叫。( ，) 8 4 4 昙一4 三0 叫+ ( ，) 一4 一 三一4 丢 或者 ( j r ) 28 4 6 等o ( 2 ) ：若，中有一个点钞属于d ，则该点不是坏点，c f ( 钉) 3 若c f ) = 3 ，则该 点从，处既不收获也不给予，且，中与移相邻的点中也有一个点属于d ，加上其他 的6 个点不可能都是坏点， 砌+ ( ，) 8 4 5 ；一2 j 1 o 若矗( 1 ，) 4 ，且 不与三面相关，则该点从，处既不收获也不给予，而其他7 个 点至少有两个点不是坏点， 叫( ，) 8 4 5 兰一2 1 o 若d ( 钉) 4 ，且u 与三面相关，我们分以下子情况讨论： ( 2 1 ) ：厂与三面不相邻，则，从秒收获吾，而另外7 个点不可能都是坏点，则 训+ ( ，) 8 4 6 善一1 三+ 1 弓1 o 第2 章平面图3 可着色的三个充分条件 ( 2 2 ) ：，与三面相邻，则点 既无收获也不给予，而另外7 个点不可能都是 坏点。若有6 个坏点，必有四个三角形与，相邻，则另一点仉必然d ( 1 t ) 24 ，则 由您，则厂从秒收获去，则 叫。( 厂) 8 4 6 薯+ 1 三o 若有5 个坏点，则另两个点最多从，面收获 ，则 硼+ ( ，) 8 4 5 三一2 吾o 若只有四个及其以下的坏点，则 叫( j r ) 8 4 4 ；一4 丢o ( 3 ) ：不妨设中的点都不属于d ，且或者有6 个坏点，或者有5 个坏点 若厂有6 个坏点，则必然与四个三面相邻，则另两个点的度4 ，则这两个点 给予面；，则 叫+ ( ，) 8 4 6 善+ 2 吾1 o 若厂有5 个坏点，或者，与四个三面相邻，则另三个点的度4 ，则这三个点给 予，面去，则 叫+ ( ，) 8 4 5 兰+ 3 吾o 或者，与三个三面相邻，则相关的六个点中必有一个点的度4 ，该点给予厂面吾， 贝。 加( ，) 8 4 5 2 2 三十l 吾。加( ，) 8 4 5 一2 主十l 砉o - 设d ( f ) = 9 由于，最多可与4 爪三角形相关，但由于g 无四元组，所以不可 能有连续的5 个坏点出现，则8 个公共点中必然有2 个非坏点，则 伽( ，) 9 4 6 吾一3 亏1 o 设d ( f ) = 1 0 由于，最多可与5 个三角形相关，但由于g 无四元组，所以不 可能有连续的5 个坏点出现，则1 0 个公共点中必然有2 个非坏点，则 伽+ ( 厂) 1 0 一4 8 三一2 三o - 2 0 第2 章平面图3 可着色的三个充分条件 设d ( f ) = 1 1 由于，最多可与5 个三角形相关，最多拥有l o + 公共点，则剩下 的一个点最多从，面处收获吾， 叫( 厂) l l 一4 1 0 善一1 三o 设d ( ，) 1 2 最多，的每个点都从，面处收获；， 例。( 厂) d ( f ) 一4 一d ( 厂) 喜0 n d 根据前述几个引理，新权重之和大予零，说明极小反例g 不存在。从而 定理2 3 1 得证。 推论2 3 1 v g f 3 ，x ( a ) 3 证明设图g f 3 ，如果g 中不含4 ，6 圈也不含7 圈，由定理1 o 3 ，图g 是3 可 着色的。若g 有4 圈、6 圈或7 圈，由定理2 3 1 ，则g 的每一个4 _ 圈，6 至1 l 圈 的孓正常着色妒都可扩充到g 第3 章进4 步的问题 第3 章进一步的问题 本文对平面图的3 着色的充分条件进行了一些研究，但这是远远不足的。 我们可以在此基础上进一步地思考 在摘要中我们提到，s t e i n b e r g 猜想：每个既不含4 一圈也不含5 一圈的平 面图是3 一可着色的e r d 6 s 猜想：是否存在整数k ，使得每个不含4 至k 圈的平 面图是3 一可着色的 依照他们的猜想和本文的讨论，我们也提出有关解决这些猜想的一些问 题： 问题l 每个不含长为4 至6 圈的平面图是3 可着色的。 易见问题1 是由猜想e r d 6 s 猜想得到为解决这个阅题，我们也可以尝试先 解决一些特殊问题 问题2 每个不含k 一圈( 4 k 6 ) ，且每个口一圈( 4 q 7 ，q 七) 都不与长度小于8 的圈有公共边的平面图是3 可着色的。 通过问题2 ，我们还可以进一步讨论，能否把长度小于8 的圈改成长度小 于7 的圈? 问题3 每个不含七一圈( 4 k 6 ) ，且每个口一圈( 4 q 7 ，q 后) 都不与长度小于7 的圈有公共边的平面图是3 可着色的， 鉴于我在本文中使用的讨论方法都是利用欧拉公式，极小反例和权转移 方法，因此，我希望自己能进一步考虑下面一个问题： 问题4 可否利用其他的方法直接证明这三个充分条件? 参考文献 参考文献 【6 】h l a b b o t t ，b z h o u ，o ms m a l lf a c e si n4 - c r i t i c a lg r a p h s ，a r sc o m b i n 3 2 ( 1 9 9 1 ) 2 0 3 - 2 0 7 【2 】o vb o r o d i n , s t u c t u e a lp r o p e r t i