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

摘要 平面图的全染色 摘要 用g = ( ve ) 表示一个顶点集为y ，边集为e 的有限、简单无 向图， 1 ，2 ，是) 表示k 个颜色的集合g 的一个正常k 全染色是 指一个映射妒：v u e 一 l 2 ，忌) 使得相邻的点、相邻的边以 及相关联的点和边都接受不同的颜色，如果g 有一个正常k 全染色， 则称g 是k 全可染的g 的全色数x r ( a ) 是使得g 可以正常k 全染 色的最小非负整数k 图g 的一个全色列表是一个颜色集合簇l ，对g 的每个元素 z vue 都配一个颜色集合l ( x ) 若g 有一个正常全染色多，使得 每个元素z v u e ，妒扛) l ( x ) ，则称g 是l 全可染的若对每一 个满足i 己( z ) f = k ，z vue 的l ，g 都是l 全可染的，则称g 是 k 全可选择的g 的列表全色数，或称全选择数c h t ( g ) 是使得g 是 盎全可选择的最小非负整数k 关于图的全染色问题，v i z i i l g 和b e h a z d 分别独立地提出了著名的 全染色猜想( t c c ) ：每个最大度为的简单图都是+ 2 全可染的， 本文主要研究了平面图的全染色和全选择性问题，证明了：对平 面图g ， ( 1 ) 若a ( a ) = 6 且g 不含相邻三角形，则g 是8 全可染的； ( 2 ) 若( g ) = 6 且g 不含4 圈和相邻5 面，则g 是7 全可染的； ( 3 ) 若a ( g ) = 9 且g 不含相邻三角形，则g 是l o 全可染的； ( 4 ) 若a ( a ) = 6 且g 不含相交三角形，则g 是8 全可选的； ( 5 ) 若a ( c ) = 1 1 且g 不含相邻三角形，则g 是1 2 全可选的 关键词：平面图，全色数，列表全色数，最大度，三角形 a b s t i 乙a c t t 0 1 a lc 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 l e tg = ( v e ) b e af 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 ht h es e t o f v e r t i c e sva n d t h es e to fe d g e se ，a n dc = 1 ，2 ，七) ，as e to f 七c o l o r s ap r o p e rk t o t a l - c o l o r i n go fgi sam a p p i n gf r o mvue i n t ocs 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 s 试vuer e c e i v e d i s t i n c tc o l o r s i fgh a sa p r o p e r 后- t o t a l - c o l o r i n g t h e ngi ss a i dt ob e 后一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 r , d e n o t e db yx r ( g ) ，i s t h es m a l l e s ti i o n - n e g a t i v ei n t e g e rks u c ht h a tgi s k - t o t a l l y - t o l e r a b l e at o t a l l i s t - a s s i g n m e n tlo fgi sas e to fl i s t so fc o l o r sw h i c ha s s i g n e a c he l e m e n tz v u eo fga l i s to fc o l o r sl ( z ) i fgh a sa p r o p e r t o t a l - c o l o r i n g 妒s u c ht h a t 砂( z ) l ( 。) f o re v e r y z vue ，t h e n gi ss a i dt ob elt o l e r a b l e gi sl - t o l e r a b l ef o re v e r yt o t a l l i s t - a s s i g n m e n tlw i t hl l ( z ) l = 兄f o re v e r yz v u e ，t h e n w es a y t h a t gi s 忌一l i s t - t o t a l l y - t o l e r a b l e ，o r 七一f 口捌砂c h o o s a b l e t h et o t a lc h o i c e n u m b e r , o r , l i s t - c h r o m a t i cn u m b e ro fg ，d e n o t e db yc h r ( c ) ，i st h el e a s t n o n n e g a t i v ei n t e g e r 七s u c ht h a tgi s | j 一幻蛔砂一c h o o s a b l e o nt o t a lc o l o r i n go f g r a p h s ，v i z i n ga n db e h a z 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 t ：e v e r ys i m p l eg r a p hgw i t hm a x i m u md e g r e eai s ( a + 2 ) 一 t o t a 一c o l o r a b l e t h i si sk n o w na s t 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 h i sd i s s e r t a t i o nm a i n l ys t u d i e st o t a lc o l o r i n ga n dl i s tt o t a lc o l o r i n go f p l a n a rg r a p h s f o rp l a n a rg r a p h sg ，w eh a v e ： ( 1 ) i fa ( c ) = 6 ，a n dgh a sn oa d j a c e n tt r i a n g l e s ，t h e ngi s 8 - t o t a l l y - o o l o r a b l e ； ( 2 ) i f a ( c ) = 6 ，a n dg h a sn o 4c y c l e so ra d j a c e n t5f a c e s ，t h e ng i s 8 - t o t a u y - t o l e r a b l e ； 一一 a b s t r a c t ( 3 ) i f ( g ) = 9 ，a n dgh a sn oa d j a c e n tt r i a n g l e s ，t h e ng i s1 0 - t o t a l l y - c o l o r a b l e ； 。 ( 4 ) i f ( g ) = 6 ，a n dg h a sn oi n t e r s e c t a n tt r i a n g l e s ，t h e ngi s 8 - t o t a l l y - c h o o s a b l e ； ( 5 ) i fa ( g ) = 1 1 ，a n dgh a sn oa d j a c e n tt r i a n g l e s ，t h e n gi s1 2 - t o t a l l y - 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 s ，t o t a lc h r o m a t i cn u m b e r , l i s t t o t a l - c h r o m a t i c n u m b e r , m a x i m u md e g r e e ，t r i a n g l e s m 一 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 己在论文中作了明确的声明并表示了谢意。 研究生签名： 筒嘲 学位论文使用授权声明 日期 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允诲论文被查阅和借阗，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 愀铭：m 哦 导师签名：z 确日期 一 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：7 扬识 指导教师：z 磊葫 一、绪论 ( 一) 、基本概念 一、绪论 在本节中，我们定义一些本文常用的图论基本术语和符号一个有序对 g = ( v e ) 称为一个无向图，其中y 是一个有限集合，e 是y 中元素的某些无 序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图g 的边通常分别 用v ( v ) 、e ( c ) 来表示图g 的顶点集合、边集合，不至于混淆的情况下可分别 简记为e ，f 没有重边和环的图叫做简单图除非特别指出，本文研究的图均指 有限简单无向图 可平面图是可以画在e u c l i d 平面上且能使得边仅在端点处相交的图平面图 则是可平面图在e u o l i d 平面上实现边仅在端点处相交的一种特殊画法平面图的 边把整个平面分割成若干个连通区域，这些区域的闭包称为平面图的面常用 f ( g ) ( 或简记为f ) 表示图g 的面的集合 常用“， 表示图g 的点，e 、，分别表示图g 的边和面若边e = “ e ( c ) ，则说点t 和口在g 中相邻，或“和口互为邻点；这时又说虹和是e 的 端点口的全体邻点所形成的集合叫做口的邻域，记作n ( v ) 若点钉是边e 的 一个端点，则说t ，与e 在g 中相关联，若顶点v ( 或边e ) 在面，的边界上，则说 t ，( 或e ) 与，在g 中相关联若e 1 ，e 2 是g 的两条边，并且有一个公共端点，则称 8 1 8 2 在g 中相邻；同样，若面，1 ，2 在g 中有公共边，则称这两个面在g 中相邻 设w 是图g 的一个顶点，与口相关联的边的条数叫做v 的度数，记作d g ( ) ，在不 至于混淆的情况下简记为d ( v ) 图g 中点的最小和最大的度数分别记作6 ( g ) 和 a ( c ) ( 或简记为6 ，) 若d ( v ) = k ( d ( v ) k ，d ( v ) k ) ，则称 为一个k 点( + 点，k 一点) 我们把一个与口相邻的k 点，叫作秽的一个k 邻点用以( 口) 表示 t ，的k 邻点的个数 在平面图g 中，面f r ( c ) ，用b ( f ) 表示围绕面，的闭途径把闭途径 b ( f ) 的长度( 若出现割边，则割边计算两次) 称为面，的度，记为d ( f ) 若d ( f ) = k ( d ( f ) k ，d ( f ) k ) ，则称，为一个k 面( k + 面，k 一面) 若两个k 面相邻， 则称它们为相邻k 面若一个面的边界是一个圈，则称这个面是一个简单面 若平面图g 是2 连通的，则它的每个面的边界都是一个圈，常用这个圈的顶点 序列来表示这个面对于3 面，= v l 地，为强调它的关联特性，常用度序列 、绪论 ( a ( v 1 ) ，d ( v 2 ) ，d c v 3 ) ) 来表示该面，另外，3 面还通常称作三角形如果两个三角 形至少有一个公共顶点，则称这两个三角形是相交三角形；如果两个三角形有一 条公共边，则称它们是相邻三角形 本文所用术语和符号基本上与文献【l 】中致本节中未介绍的其他图论术 语将在必要时予以阐述 ( - - ) 、全染色问题的研究概况与本文的研究工作 图的染色理论是图论中最重要的分支之一，在无线通讯频道分配、舰队维 护、任务分派、交通定向等诸多领域都有着广泛的应用，见文献 2 】随着点染色 和边染色的发展，图的全染色，即对图的点和边同时进行正常染色，也被相继提了 出来本文主要研究了平面图的全染色以及平面图的全选择性问题另外，还对一 些特殊图的全染色进行了初步探讨 最初，v i z i n g 和b e h a z d 单独提出了图的全染色概念 定义1 1 若有一个映射：y ( 回u e ( g ) 1 ，2 ，女 满足以下三个条件： ( i ) 若两个点v l ，耽v ( g ) 相邻，且有( 口1 ) ( 2 ) ； ( i ) 若两条边e l ，e 2 e ( g ) 相邻，且有( e 1 ) 咖( 8 2 ) ； ( i i i ) 若点秽和边e 在g 中相关联，且有( 口) 妒( e ) 则称西是图g 的一个正常全染色 定义图g 的全色数为x r ( g ) = m 饥( k l g 有一个正常k 全染色) 若g 有 一个正常女全染色，则称g 是k 全可染的除非特别声明，图g 的k 全染色均 指正常k 全染色 显然，对于任意一个图g ，愆f g ) a ( g ) + 1 b e h a z d 3 1 在19 6 5 年和v i z i n g 【4 】在1 9 6 8 年各自独立地提出了著名的全染色猜想( t c c ) ： 猜想1 1 每个最大度为的简单图都是+ 2 全可染的 ( 实际上，v i z i n g 提出的是更一般的全染色猜想：对每个多重图g ，有 x r ( g ) ( g ) + p ( g ) + 1 ，其中，z ( g ) 表示g 的最大重数，) 一2 一 一、绪论 对于最大度as2 的图g ，珩( g ) + 2 是很显然的1 9 7 1 年，r o s e n f e l d 【5 】和v i i a y a d r y a1 6 分别用不同的方法( 前者是对图g 的阶数进行数学归纳，后者 是把图g 分解成1 因子和2 因子) 证明了 定理1 1 对最大度6 ( a ) = 3 的简单图g ，t c c 是成立的 1 9 7 7 年，k o s t o o h k a 7 得到了 定理1 2 若g 是最大度a = 4 的简单图，则x r ( a ) 6 ，即t c c 成立 由于在7 0 年代研究这个问题的人较少。进展就显得比较缓慢直到8 0 年代后 期才有越来越多的学者重耨开始研究该课题，直至q 现在仍然有很多学者对此深感 兴趣，也得到了很多好的结果 k o s t o c h k a 8 证明了 定理1 3 对任意= 5 的简单图g ，t c c 是成立的 与此同时，不少学者对最大度较大的图进行了研究 h i l t i o n 和h i n d 【9 】合作证明了 定理1 4 t c c 成立，如果图g 的最大度( g ) i g l m o l l o y 和r e e d 【1 0 】证明了 定理1 5 如果图g 的最大度充分大，则x t ( g ) a + c ，c 是一个较大的常数 在平面图的全染色方面，t c c 更是得到了很好的验证， b o r o d i n 【l l 】等人证明了 定理1 6g 是一个平面图，则 ( 1 ) x r ( a ) + 2 ，若a 6 ，7 ，8 ； ( 2 ) x r ( g ) s + 3 ，若 6 ，7 ，8 ) ； ( 3 ) x t ( g ) = + 1 ，若a ( g ) 1 4 一3 一 随后，y a p 【1 2 】证明了 定理1 7 对于最大度a ( a ) 8 的平面图g ，t c c 是成立的 s a n d e r s 和z h a o 1 3 】证明了 定理1 8 最大度a ( a ) 7 的平面图是9 全可染的，即对a ( a ) = 7 的平面图来 说，t c c 是成立的 研究过程中，有些学者在最大度的条件基础上了又对图g 的围长进行了限 定，也得到了不少好的结果吴建良【1 4 】等人证明了 定理1 9 对于围长9 4 的平面图g ，t c c 是成立的 综上所述，对平面图来晚只剩下z x ( a ) = 6 的情况依然没有被完全解决最 近，王应前和上官敏乐【1 5 】证明了 定理1 1 0 对a ( g ) = 6 且不含4 圈的平面图g ，t c c 是成立的 本文对这个结果作了进一步的改进，将在第二章证明 a ( a 1 = 6 且不含相邻三角形的平面图g 是8 全可染的，即t c c 是成立的 随着研究的深入，人们有意思地发现很多图类g 不仅满足t c c ，而且它们 的全色数还能取到相应的下界，也就是说x r ( a ) = + 1 因此，类似边染色的 分类问题( v i z i i i g 【1 6 】确定7 z x ( a ) ( g ) a ( a ) + 1 ，并称) ( ( g ) = ( g ) 的简 单图g 为第一类的，其余的简单图为第二类的) ，根据全色数对图进行了分类：若 x r ( a ) = + 1 ，则称g 是第一型的；若x t ( g ) = + 2 ，则称g 是第二型的 张忠辅【17 】等人证明了 定理1 1 1g 是3 的外平面图，则胎( g ) = a + 1 b o r o d i n 等人在文献 1 8 = p i e n 了 一正一 一、绪论 定理1 1 zg 是一个平面图，围长为g ，最大度为，若g 满足下列条件之一，则 x r ( g ) = a + 1 ( 1 ) a 1 1 ； ( 2 ) 7 ，且g 4 ； ( 3 ) a 5 ，且g 5 ； ( 4 ) a 4 ，且g 6 ； ( 5 ) a 3 ，且g 1 0 最近，王维凡【1 9 f i e 明了 定理1 1 3 若g 是最大度a = 1 0 的平面图，则x t ( g ) = 1 1 本文将在第二章中分别证明： ( 1 ) 若g 是最大度= 6 且不含4 圈和相邻5 面的平面图，则x r ( g ) = + 1 = 7 ： ( 2 ) 最大度为9 且不含相邻三角形的平面图g 是第一型的 另外，最近有学者对一些特殊的图类做了研究，也得到了一些有意思的结果， 例如李光荣和张力民【2 0 】证明了 定理1 1 4 若仃2 ，则图g = k ，也。l + r 是第一型的 定理1 1 5 若“2 礼l 1 ，m 1 ，则图g = 取。，m + p 是第一型的 本文将在第四章和第五章中分别给出一类联图和一些特殊图的全染色，确定 它们的全色数 图g 的一个全色列表是一个颜色集合簇l ，对g 的每个元素z v u e 都 配一个颜色集合l ( z ) 若g 有一个正常的全染色妒，使得每个元素z vu e ， 妒( z ) l ( x ) ，则称g 是l 全可染的若对每一个满足i 三( o ) 1 ，o v u e 的 全色列表l ，g 都是三全可染的，则称g 是全可选择的g 的列表全色数，或称 全选择数c b ( g ) 是使得g 是全可选择的最小的非负整数 下面介绍两个著名的列表全染色猜想 猜想1 2 对简单图g ，有c h r ( c ) ( g ) + 2 j u v a a 【2 l 】等人首先证明了对于任意曼3 的简单图，该猜想是成立的 随着研究的发展，该猜想又得到了进一步的加强，于是提出了下面的猜想，简 记作l t c c 猜想1 , 3 对每个简单图g ，都有c h r ( g ) = x r ( g ) 在平面图方面，l t c c 得到了很大进展 b o r o d i n k o s t o e h k a 和w o o d a l l 2 2 证明了 定理1 1 6最大度和围长g 满足以下条件之一的平面图g ，都有c h r ( g ) = x r ( o ) = ( g ) + l ，即l t c c 成立 ( 1 ) 1 6 且g 3 ； ( 2 ) a 7 且g 4 ； ( 3 ) a 6 且g 5 ； ( 4 ) a 5 且g 6 ； ( 5 ) a 4 且g 1 0 王维凡在 2 3 1 和 2 4 1 也相继证明了 定理1 1 7g 是一个外平面图，当a 3 时，c h t ( g ) 5 ； 当4 时，c h t ( g ) = 珩( g ) = a + 1 定理1 1 8 对4 的h a l i n 图g ，c 知r ( c ) = x r ( o ) = a + 1 侯剑锋【2 5 】证明了 定理1 1 9g 是最大度为并且不含4 到圈的平面图，其中k 4 若g 满足 下面条件之一，则c h t ( g ) = + 1 ( 1 ) a 27 且k 4 ； ( 2 ) 6 且k 5 ； 一6 一 一，绪论 ( 3 ) 5 且k 8 关于平面图的全选择性问题本文将在第三章中分别证明： ( 1 ) 最大度= 6 ，且不含相交三角形的平面图g 是( + 2 ) 全可选择的； ( 2 ) 若g 是最大度= 1 1 且不含相邻三角形的平面图，则c h t = x r ( c ) = 1 2 最后，本文在第六章给出有关全染色的一个小节，简单叙述了全染色的后续 研究课题，并给出了几个可能对后续研究有用的引理 二、平而刚的全染色 二、平面图的全染色 ( 一) 、最大度为6 的平面图的全染色 对于平面图来说，全染色猜想( t c c ) 仅剩下a ( g ) = 6 的情形仍是公开问题 尽管该问题还没有被完全解决，但也已经取得了有意义的进展，参考文献 1 5 1 本 节首先将对该结果稍加改进，证明 定理2 1若g 是一个= 6 且不含相邻三角形的平面图，则g 是8 全可染的 给图g 的每个顶点或边。分配一个颜色列表l ( x ) ，若对每个x vue ，都 可从l ) 中选择出一个颜色染给z ，使得任意两个相邻或相关联的元素接受不 同的颜色，则称g 是l 全可染的若对g 的每一个全色列表l ：弘( z ) i l 扛) k ，z v 1 je ) ，g 都是l 全可染的，则称g 是全可选择的用c k 表示长度为 竹的圈，不难证明 引理2 1圈c _ 是4 全可选择的 假设定理2 1 不成立，即存在着满足定理2 1 的假设而不是8 全可染的简单平 面图设g 是使得a ( g ) = i v l 土i e 尽可能小的这样一个平面图，不难得到g 的 如下性质 引理2 2g 是2 连通的，从而j 芝2 且g 的每个面的边界都是圈 引理2 3设删是g 的一条边若d ( v ) 3 ，则d ( u ) + d ( 口) 2 + 3 = 9 特别 地，g 不含有2 点，3 点只能和6 点相邻 证明：假设g 中存在着d ( v ) 3 且d ( u ) + d ( ) s8 的边由口( g ) 的极小性 可知，g 7 = g 一伽是8 全可染的设g 已获得8 全染色抹去 点的颜色后，待 染的边u 口至多有7 种颜色不能用，故可将边删染好最后，由于d ( 口) 3 ，秽至 多有3 2 = 6 种颜色不能用，即口至少还有8 6 = 2 种颜色可用，从而可以将 点口重新染好，进而得到了g 的一个8 全染色，这与g 不是8 全可染的矛盾 一s 一 二、平而网的垒染色 引理2 4 g 中不含有d ( v 1 ) = d ( v 3 ) 一= d ( v 2 k 一1 ) = 3 的偶圈q k = v l v 2 。忱k 证明：假设g 中存在着d ( 口1 ) = d b ) 一r = d ( v 2 女一1 ) = 3 的偶圈岛k = 口1 吨v 2 k 由引理3 知d ( v 2 ) = d ( v 4 ) 一= d ( v 2 k ) = 6 根据o ( g ) 的极小性， g 7 = g e ( 岛 ) 是8 全可染的设g 已获得8 全染色抹去口1 ，v a ， 2 k i 的 色后，待染的c 2 中的每一条边都至少还有2 种颜色可用因为偶圈是2 边可选 择的，故可将e ( q ) 染好最后，易将v l ，砚 一1 重新染好，从而g 是8 全 可染的，矛盾 引理2 5g 中不含由4 点构成的圈 证明：反设g 含有圈g = v l u 2 使得d ( v i ) = 4 ，j = 1 ，2 ，n 根据 盯( g ) 的极小性，口= g e ( g ) 是8 全可染的设g 已获得8 全染色抹去 口1 ，”2 ，的色后，c k 的每一个元素( 点或边) 都至少还有4 种颜色可用，根据 引理2 2 ，可进一步将g 的元素全部染好，从而得到整个图g 是8 全染色，矛盾 引理2 6 g 中不含图2 - 1 所示的两种3 面( 图中标有的点在原图中没有其他 邻点) ( a )( 易) 图2 - 1 证明：假设g 中含有如( a ) 所示的3 面，= 口l 2 v a ，其中d ( v 1 ) = 3 ，令g ，= g t ) l v 2 ，由极小性可知，则存在g 7 的一个8 全染色妒抹去点”1 的颜色， 在v 2 处至少还有+ 2 一( 一1 + 1 ) = 2 种颜色没有出现，并且这两种颜 色必定是妒( ”1 ) 和i ，o ( v l v 3 ) ( 否则就有一种可以染给v 1 7 ) 2 ) 在处至少还 有+ 2 一( + 1 ) = 1 种颜色没有出现，不妨设为l ，如果1 妒h 口) ，就将 一9 一 二、平两罔的全染色 # ( v l v 3 ) 染给边v l v 2 ，将1 染给v 1 ，如果l = 妒( 口1 甜，) ，则把妒( 口2 v 3 ) 染给v l v 2 ，将 口2 重染上1 ，然后很容易将点秽1 的色补染好这样就得到整个图g 的8 全染色， 矛盾 假设g 中含有如( b ) 所示的3 面，= 1 v 2 v 3 ，其中d ( v 1 ) = d ( v 2 ) = 4 ( 如图所 示) 令= g y l v 2 ，由极小性可知，g 7 是可以8 全染色的首先抹去口1 ，口2 的 颜色，重新染口1 ，v 2 ，使之染不同的颜色对于v l ，目前有6 种禁用色，很容易就 可以染好对于现，与之相邻或关联的元素有6 个，再加上”l ，故共有7 种禁用 色，因此也可以将w 2 重新染好下面就来染边v f l ) 2 若存在某种颜色即不在”1 出 现，又不在”2 出现，则就可以将这种颜色染给饥v 2 ，这样就得到了整个图g 的8 全染色，矛盾因此，我们可以假设在口1 出现的色在吨不出现，同样在耽出现的 色在”l 也不出现( 在g ，中，与v l ，口2 相关联的元素加上m ，v 2 恰好8 个) 显然在 口3 上至少还有一种颜色没有出现，不妨设为颜色1 ，如果1 在”1 ( 或v 2 ) 上不出现， 就将l 染给。1 ”3 ( 或v 2 v 3 ) ，然后将口l ”3 ( 或，0 2 u 3 ) 的色染给v l v 2 ，这样便得到了整 个图g 的8 全染色，矛盾 定理2 1 的证明 设g 是定理2 1 的一个使得口( g ) = i v i + i e i 最小的反例，由握手原理以及 边与面的关系，我们可以将平面图的欧拉公式 y j jej + f - 2 改写成 ( 2 即) 一6 ) + ( d ( ，) - 6 ) = 一1 2 v，f 现在给g 的点”分配权伽( ”) = 2 d ( v ) 一6 ，给g 的面，分配权叫( ，) = d ( f ) 一6 ，所以g 的点和面的权和。y 。f w ( x ) = - 1 2 然后根据下面的权转移 规则，重新分配点和面的权，得到。，。， 7 ( z ) 0 因为只是在点和面之间进 行权转移，故权数总和应该保持不变，便得出证明定理所要的矛盾，即定理2 1 得 证 权转移规则 二，平而罔的垒染色 r i ：4 点转 给相关联的面； r 2 ：5 + 点转；给相关联的3 面； r 3 ：5 点转i 1 给相关联的4 ，5 面； r 4 ：6 点转；给相关联的4 ，5 面 因为g 不含有相邻三角形，所以每个k 点至多与嚏j 个3 面相关联，下面来 考察顶点的新权： 3 点的新权，由上面的规则可以看出3 点的权不变，所以 7 ( ”) ( ”) = 2 3 6 = 0 4 点的新权由r l 知， t 0 7 ( ) ( t ，) 一4 = 2 4 6 2 = 0 5 点的新权由i 匕和j r 3 知， 7 扣) 伽( 口) 一2 2 3 x = 2 5 - 6 - 4 = 0 6 点的新权m r 2 和r 4 知，蜘( 口) ( 口) 一3 x ；一3 2 = 2 x 6 6 6 = 0 再来考虑面的新权 首先，检验3 面的新权根据引理2 5 和引理2 6 可知3 面必定和两个 5 + 点相关联，另外一个是4 + 点则 7 ( ，) ( ，) + 2xi + = 3 6 + 3 = 0 其次检验4 面的新权由引理2 3 和引理2 4 可知4 面不能与两个3 点 相关联如果4 面中含有一个3 点，则由引理2 3 知与其相邻的两个点一 定是6 点，根据r 4 ，7 ( ，) 叫( ，) + 2 ；+ = 0 ；否则，根据r 2 ，r 3 ，r 4 ， 伽7 ( ，) ( ，) + 4x 1 = 4 6 + 2 = 0 再检验5 面的新权显然5 面至少关联两个4 + 点，所以”( ，) w ( f ) + 2 = 5 6 + 1 = 0 对于6 + 面，来说，甜( ，) = ”( ，) 0 至此，对每一个z vu f ， 7 ( z 0 已得到验证，即定理2 1 得证 随着研究的深入，发现很多平面图的全色数能达到它的下界+ 1 ，即很多 平面图是第一型的( g ) 1 0 的情况分别被b o r o d i n 【1 8 ，王维凡【1 9 】等人先后 证明了) ( 丁( g ) = + 1 下面将用d i s = h a r g i n g 方法来证明 二、平而降l 的全染色 定理2 2g 是一个a = 6 且不含4 一圈和相邻5 面的平面图，贝u x t ( g ) = 7 ，即 g 是第一型的 假设定理2 2 不成立，g 是一个使得a ( a ) = i v l + i ej 最小的反例，显然弓 理2 2 仍然成立，且可以得到g 的如下几个性质 引理2 7 若删e ，且d ( 口) 3 ，则有d ( u ) + d ( ) + 2 = 8 特别地， g 中2 点只能和6 点相邻 证明：假设g 中存在一条边伽，d ( u ) + d ( v ) a + 1 = 7 ，且d ( v ) 3 由g 的 极小性可知，g 7 = g 删是7 全可染的假设妒是g 的一个7 全染色，现在抹 去u 点的颜色，因为边至多有( + 1 ) 一2 + 1 = 6 个颜色不能用，故可将边 u v 染好现在重新给 染色由于d ( v ) 3 ，至多有3 2 = 6 个颜色不能用，从 而可以将点口染好进而得到了g 的一个7 全染色这与g 不是7 全可染的矛盾 引理2 8 g 中不含有同构于图2 2 中( a ) ，( b ) ，和( c ) 的子图( 图中标有的点在原 图中没有其他邻点) ( a ) “2“4 ( 6 ) 图2 2 “o 3 距2 ( c ) 4 3 m 0 证明：( 8 ) 假设存在此构型根据g 的极小性，g w 存在一个7 全染色 妒抹去点口和。的染色令妒( 口”) = 1 ，我q , - i 以假设1 色在t 的点不出现， 即妒( “) 1 ，妒( e ) 1 ，e 是任意一条与u 相关联的边因为在t 点至少还有 + 1 一( a 一1 + 1 ) = 1 种颜色没有出现，如果l 色在“点出现，则就将未出现 的色染给u 因为c z ( v w ) = 1 在“的点不出现，则路u * m u 2 c 中三条边染不同的染 一1 2 二、平而刚的全染色 色，依次为1 ，2 ，3 根据妒( z z 7 ) = 1 或妒( z z 7 ) 1 ，可以将三条边重染为2 ，1 ，2 或 1 ，2 ，1 则可以将3 染给1 1 , 0 这样g 中的边就全部染好了，最后很容易将点口和 。染好，从而得到了整个图g 的一个( + 1 ) 一全染色矛盾 ( b ) 根据g 的极小性，存在g 一乱1 u 5 的一个7 全染色毋，不妨设色集 是 1 ，2 ，7 ) ，假设在t 5 处出现的色集是s ( u 5 ) 1 ，2 ，6 ) ，且咖( ) = 1 ，妒( 讹u ) = j ，i = 2 ，3 ，4 然后抹去点“1 ，蛳的色若咖( u l u 2 ) 7 ，则可以将 7 染给? 2 1 u 5 所以假设( u 1 2 ) = 7 ，若7 隹 咖( 呦让3 ) ，( 蝴“4 ) ) ，则把1 “5 染3 ，把 牡5 u 3 染7 若2 簪( 蛳3 ) ，妒( 均“4 ) ，调换u l t , 2 和u 2 u 5 的颜色，将3 染给让1 u 5 ， 把u 5 蝴染成2 因此可以假设 妒( t o 3 ) ，咖( “3 札4 ) ) = 2 ，7 ) 把4 染给“1 u 5 ，若 ( ”3 m ) = 7 ，则调换坳钆4 和u 4 u 5 的色若咖( u s u 4 ) ；2 ，则调换? _ 3 u 4 和u 4 u 5 ， 缸1 地和u 2 u 5 的色即可这样就将整个图g 所有的边染好，很容易将点“1 ，u 3 补染 好，从而得到整个图g 的7 全染色与g 是最小反例矛盾 0 ) 同( b ) 的证明 引理2 , 9岛。是3 - 全可选择的 引理2 1 0g 中不含岛= v l v 2 v 3 ，d ( v 1 ) = 4 ，i = 1 ，2 ，3 证明：若存在，根据g 的极小性，存在g e ( 岛) 的7 全染色妒，然后抹去 口1 ，7 1 2 ，v 3 的色，这样对v x v ( g ) u e ( 岛) ，每一个元素都有3 种染色可用，由引 理2 9 便可以得到整个图g 的一个7 全染色矛盾 类似与引理2 4 的证明，我们可以得到： 引理2 1 1 g 中不含d ( 1 ) = d ( v a ) 一= d ( 2 一1 ) = 2 的偶圈q k = 1 忱。1 ) 2 k 定理2 2 的证明 令g 2 是由所有与2 点相关联的边导出的子图根据引理2 7 ，g 2 中不舍有奇 圈，再由引理2 1 1 可知g 2 是个森林，并且所有的叶子都是最大度点对g 2 的每 一个分支r ，如果v ( t ) 5 ，则存在一个匹配m ，使得所有的2 点与某个最大度 点相匹配选最大度点u 作为t 的根，则称匹配每个2 点口的最大度点 t o 为支持 点如果v ( t ) = 3 ，即是一条路 0 1 w 忱，则称 1 ，忱均为2 点 的特殊支持点如 图2 3 所示 二、平而图的全染色 图2 3 v l v v 2 g 是定理2 2 的一个使得口( g ) = 【v l + i e l 最小的反例，由握手原理以 及边与面的关系，我们可以将平面图的欧拉公式j y i f ej + i ，f = 2 改写成 v e v ( 2 d ( v ) 一6 ) + ( d ( ，) 一6 ) = fef - 1 2 现在给g 的点钞分配权 ( w ) = 2 d ( v ) 一6 ，给g 的面，分配权w ( ) = d ( f ) 一6 ，所以g 的点和面的权和。；y 。f 铷( z ) = 一1 2 然后根据下面的权转移 规则，重新分配点和面的权，得到。；v 。_ p ( 。) 0 因为只是在点和面之间进 行权转移，故权数总和应保持不变，使得出证明定理所要的矛盾，即定理2 2 得证 权转移规则： r 1 ：6 点作为支持点转2 给相邻的2 点，作为特殊支持者转1 给相邻的2 点，转i 给相关联的( 4 ，5 + ，6 ) ，转 给其他的3 面，给相关联的5 面； r 2 ：5 点转；给相关联的3 面，给相关联的5 面； r 3 ：4 点转；给相关联的3 面，转 给相关联的5 面 下面来考察顶点的新权： 3 点的新权由上面的规则可以看出3 点的权不变，所以训7 ( 口) = w ( v ) = 2x3 6 = 0 4 点的新权由于g 不舍4 圈和相邻5 面，并根据i t 3 ， t o ( t ，) = ( 口) 一2 i 一2x = 2 4 6 2 = 0 5 点的新权由于g 不含4 圈和相邻5 面，5 点口至多关联两个3 面和两 个5 面根据r 2 ，叫7 ) 鲫( t ，) 一2 ；一2 = 2x5 6 3 一； 0 6 点的新权6 点的新权将分以下3 种情况来讨论 情况1 当6 点t ，与2 点相邻，且2 点与3 面相关联由引理2 8 可知， 是 该2 点的特殊支持者，不可能再和其他2 点相关联又台不含4 圈和相邻5 面，若 二、平丽罔的全染色 t ，另外关联两个( 4 ，4 ，6 ) 和两个5 面，根据引理2 7 可知，同时与两个( 4 ，4 ，6 ) 相 关联的那个5 面的另外两个点都是4 + 点，此时6 点可以不给该5 面权，所以 卸扣) ( t ，) 一1 3 ；一 0 否则，( t ，) ( 移) 一1 2 ；一；一2 0 情况2 当6 点口与2 点相邻，但2 点不与三角形相关联 3 是一个2 点的支 持者，要转给该2 点2 又因为g 不含4 图和相邻5 面，故 至多关联两个3 面和3 个5 面，故伽 ) 叫 ) 一2 2 ；一3 ；= 0 情况3 6 点不与2 点相邻此时w 7 ( t ，) ( 口) 一3 ；一3 ； 0 最后来考虑面的新权 首先，检验3 面的新权 若3 面，与一个3 一点相关联，则根据引理2 7 ，另外两个点一定是5 + 点，则 铷7 ( ，) = ( ，) + 2x ；= 3 6 + 3 = 0 若3 面相关联的点都是4 + 点，又由引 理2 1 0 ，3 面不可能是( 4 ，4 ，4 ) ，所以 7 ( ，) = w ( ) + 2 i + ；= 3 6 + 3 = 0 g 不含4 圈，故没有4 面 再检验5 面的新权 若5 面关联两个3 一点，则根据引理2 7 ，另外3 个点必定是5 + 点，故w 7 ( ，) = t j ( ，) + 3 i 1 = 0 若5 面相关联一个3 一点，根据引理2 7 ，与该3 一点相邻的两个点 必定是5 + 点，另外两个是4 + 点，所以钟( ，) ( ，) + 2 1 + 2x ； 0 若5 面 不关联3 一点，显然叫7 ( ，) 叫( ，) + 4 = 6 6 + 1 = 0 对于6 + 面，来说，”7 ( ，) = “，( ，) 0 因此，对g 中顶点和面经过权的重新分配后得到了我们所希望的矛盾即定 理2 2 得证 ( - - ) 、最大度为9 的平面图的全染色 已证明= 9 的平面图满足全染色猜想f r c c ) , 并且l o 的平面图都是 + 1 全可染的= 9 的平面图是不是+ 1 全可染的呢? 这个问题目前还没 有得到证实，下面将证明 定理2 3若g 是= 9 且不含相邻三角形的平面图，则g 是1 0 全可染的 一1 5 一 二、平而圈的全染色 假设定理2 3 不成立，即存在着满足定理2 3 的假设而不是l o 全可染的简单 平面图，设g 是使得口( g ) = j vj + e l 尽可能小的这样一个平面图显然对于g ， 引理2 ，2 仍然成立并且还可以得到如下性质 引理2 1 2设倒是gn - - 条n 若d ( ) 4 ，则d ) + d ( t j ) 1 1 特别地，2 点只能和9 点相邻 i i