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

， 平面图的线性染色 摘要 l i l ll l li iii ii ii iii i iu i 18 0 4 7 8 3 用g = ( ve ) 表示一个有限简单无向图，顶点集为y ，边集为e 如果g 的 一个映射咖：y 一 1 ，2 ，七) 满足当让口e ，有( u ) 咖( u ) ，则称是g 的 一个正常七染色若g 有一个正常七染色，则称g 是k 可染的图g 的线性染 色是g 的一个正常染色使得染任意两种颜色的顶点集合导出子图是一些点不交 的路的并图g 的所有线性染色中所用的最少颜色的个数称为g 的线性色数，用 l c ( g ) 表示 1 9 7 3 年，g r i i n b a u m l l 】提出了无圈染色的概念，图g 的一个使得染任意两种颜 色的顶点集合导出子图是一个森林的正常染色称为g 的一个无圈染色1 9 9 8 年。 y u s t e r 2 1 提出了图的线性染色概念，并证明了任意图g 都有l c ( c ) = 0 ( ) ，同时 构造出了一类图满足l c ( g ) = q ( 量) 事实上，图的线性染色是无圈染色的一种 特殊情形 本学位论文改进和扩充了关于平面图线性染色的一些已有结果设和 g ( c ) 分别为图g 的最大度和围长本文的主要结果如下： ( 1 ) 对一个平面图g ，若a 6 ，则i c ( g ) 2 a + 1 ；若7 ，则l c ( g ) 2 a ； ( 2 ) 若g 是一个g ( c ) 61 拘- - 7 面图，则i c ( g ) f 会 + 3 ；且当a 岳 4 ，5 ，1 2 ) 时，有l c ( g ) 会1 + 2 ； ( 3 ) 若g 是一个g ( c ) 5 的平面图，则i c ( g ) 会 + 5 ；且当a 譬 7 ，8 ，1 4 ) 时，有l c ( g ) i a - - 4 ； ( 4 ) 若g 是g ( c ) 4 的平面图，则l c ( c ) 等 - t - 2 关键词：线性染色；平面图；最大度；围长 ， 一t ， 彳 一 l | n e a rc 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 l e tg = ( v e ) b eaf 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 hv e r t e xs e tva n d e d g es e te ap r o p e rk - c o l o r i n go fg i sam a p p i n g ：v 叫 1 ，2 ，七) s u c ht h a t ( 让) ( 秽) i fu e al i n e a rc o l o r i n gi sap r o p e rc o l o r i n gs u c ht h a tt h eg r a p h i n d u c e db yt h ev e r t i c e so fa n yt w oc o l o rc l a s s e si st h eu n i o no fv e r t e x d i s j o i n tp a t h s t h el i n e a rc h r o m a t i cn u m b e ro fg r a p hgi st h es m a l l e s tn u m b e ro fc o l o r si nal i n e a r c o l o r i n go fg ，d e n o t e db yl c ( a ) i n19 7 3 ，g r t i n b a u m 1 1i n t r o d u c e dt h ea c y c l i c c o l o r i n go fg r a p hg ，w h i c hi sap r o p e r v e r t e xc o l o r i n go fgs a t i s f i e dt h a ta n yt w oc o l o rc l a s s e si n d u c eaf o r e s t i n19 9 8 ， y u s t e r 2 】f i r s ti n t r o d u c e dt h el i n e a rc o l o r i n go fg r a p h sa n ds h o w e dl c ( c ) = d ( ；) f o ra n yg r a p hga n dc o n s t r u c t e dag r a p hgs u c ht h a tl c ( g ) = q ( ；) i n d e e d ，l i n e a r c o l o r i n go fg i sas p e c i a lc a s eo fa c y c l i cc o l o r i n g h lt h i sm a s t e rt h e s i s w ee x t e n da n di m p r o v es o m ek n o w nr e s u l t so nt h el i n e a r c o l o r i n go fp l a n a rg r a p h w eu s ea a n dg ( c ) t od e n o t e ，r e s p e c t i v e l y , t h em a x i m u m d e g r e ea n dg i r t ho fg m a i nr e s u l t sa r ea sf o l l o w s ： ( 1 ) e v e r yp l a n a rg r a p hg h a si c ( g ) s2 a + 1 i f a 6 ，l c ( g ) 2 ai fa 7 ； ( 2 ) l e tg b ea p l a n a rg r a p hw i t hg ( c ) 6 ，t h e nl c ( g ) 今 + 3 ；a n di fa 芒 4 ，5 ，1 2 ) ，t h e nl c ( g ) s 会 + 2 ； ( 3 ) l e tg b eap l a n a rg r a p hw i t hg ( c ) 5 ，t h e nl c ( g ) 会 + 5 ；a n di fa 隹 7 ，8 ，1 4 ) ，t h e nl c ( g ) 会 + 4 ； ( 6 ) e v e r yp l a n a rg r a p hg w i t hg ( g ) 4h a sl c ( g ) f 等 + 2 k e yw o r d s ：l i n e a rc o l o r i n g ；p l a n eg r a p h ；m a x i m u md e g r e e ；g i r t h i i _ 目录 摘要 i a b s t r a c t l i 目录 1 绪论l 1 1 基本概念1 1 2 线悄! 染色的研究现状1 1 3 本文的j l i 要：【：作4 2 平 f l f 躅线性色数的个i ：界5 2 1 a s6 的情形6 2 2 7 的妫i 形1 5 3 嘲长伞少为6 的、犷i f i i 矧的线r 卜染色勰 3 1 调殳1 ：界f ( g ) 2 j + 3 2 8 3 2 | | ；分改进的上界陋( ( 7 ) 2 1 + 2 3 l 4 阉长至少为5 的半晒图的线性染色加 4 1 一般l ：猝f ( ? ) 2 1 + 5 4 0 4 2 部分改进昀卜界( g ) 2 1 + 4 4 4 5 嘲长肇少为4 的乎峨图的线住染色5 3 参考文献印 攻读学位期间取得的研究成巢6 3 致谢6 4 浙江师范大学学位论文独创性声明6 5 r 学位论文使用授权声明6 5 学位论文诚信承诺书6 6 i v 1 1 基本概念 1 绪论 本节定义一些图论基本术语和符号一个有序对g = ( ve ) 称为一个无向 图，其中y 是一个有限集合，e 是y 中的不同元素的无序对的集合y 中的元素 叫做图g 的顶点，e 中的元素叫做图的边用y ( g ) ，e ( g ) 分别表示图g 的顶 点集合与边集合，用l v ( g ) i ，i e ( g ) 1 分别表示g 的点数与边数没有环和重边的 图叫简单图本文研究的图均指有限简单无向图对于图g 中顶点札和t ，若边 e = t i e ( g ) ，则称t | 和v 相邻，让和u 互为邻点，让和秒分别与e 关联我们称 面，和它的边界上的顶点和边是关联的，至少有一条公共边的两个面是相邻的 把与一个顶点t ，关联的边数叫做v 的度，记作d g ( ) 用6 ( g ) 和( g ) 分别表示 g 的顶点的最小度和最大度u 的全体邻点称为移在图g 中的邻域，记作n c ( 移) 把图g 中最短圈的长度称为g 的围长，记为夕( g ) 在不产生混淆的情况下，把 i v ( g ) i ，l e ( g ) i ，n o ( v ) ，d c ( 口) ，6 ( g ) ，a ( g ) 分别简记为i y i ，l e l ，( u ) ，d ( ) ，6 ，a 若一个图能画在平面上使得它的边仅在端点相交，则称这个图是可平面图 可平面图的这种画法称为图的平面嵌入，或称为平面图对平面图g ，用f ( g ) 表 示面集合对于，f ( g ) ，用6 ( ，) 来表示面，的边界，= u l u 2 u n 】表示边界 点顺时针方向依次为u 1 ，u 2 ，t t i 的面，这里点是允许重复出现的称面，和 它边界上的顶点和边是关联的面的度d g ( ，) 是指和g 中面，关联的边的条数， 其中割边被计算两次，简记为d ( ，) 一个度数为k 的顶点( 面) 被称为k 点( 七面) ， 一个度数至少为k 或至多为k 的顶点( 面) 被称为扩点( 扩面) 或k 一点( k - 面) 本文其它未定义而直接使用的术语和符号请参阅文献【3 】本节中未介绍的 其他图论术语将在必要时予以阐述 1 2 线性染色的研究现状 图染色问题源自著名的四色问题关于平面图的染色问题是图论界的热点也 是难点图的染色理论也是图论中最重要的分支之一，在交通定向、任务分派、 舰队维护、无线通讯频道分配等诸多领域都有广泛应用，见文献 4 】 1 1 绪论 g 的一个映射砂：y 一 1 ，2 ，七】满足当u v e ，有咖( u ) 妒( ) ，则称妒 是g 的一个正常k 染色若g 有一个正常k 染色，则称g 是k 可染的关于平面 图顶点染色问题已经在【5 1 2 】得到了广泛的研究 线性染色的概念是由y u s t e r 2 在1 9 9 8 年最先提出的图g 的线性染色是g 的一个正常染色使得染任意两种颜色的顶点集合导出子图是一些点不交的路的 并图g 的线性色数是指g 的所有线性染色中所用的最少颜色的个数，用l c ( g ) 表示y u s t e r 证明了对任意图g ，有l c ( g ) = d ( ；) ，同时构造出了一类图满足 l c ( g ) = q ( i ) 事实上，图的线性染色是无圈染色的一种特殊情形图g 的一 个使得染任意两种颜色的顶点集合导出子图是一个森林的正常染色称为g 的一 个无圈染色g r t i n b a u m 1 】提出了无圈染色的概念，而无圈染色已经在文献【1 3 2 l 】 中深入研究 另一个和线性染色相关的概念是k f r u g a l 染色图g 的一个k f r u g a l 染色是 g 的一个正常染色，使得g 的任意一个顶点的邻域中最多有k 个顶点染相同颜 色图的线性染色显然是2 - f r u g a l 染色，而k f r u g a l 染色在文献【2 2 2 7 】中深入研 究 2 0 0 8 年，e s p e r e t , m o n t a s s i e r 和r a s p a u d 2 s l 提出了线性选择性的概念，这是线 性染色的一个推广若顶点色列表l 是图g 的一个颜色集合簇，g 的每个顶点 对应一个颜色集合l ( 口) 如果有g 有一个线性染色c 使得对g 每个顶点口， c ( v ) 三( ) ，则称g 是线性工可染的，c 是g 的一个线性l 染色对一个厶只 要工满足对所有的t ，y ( g ) ，l 三( t ，) i k ，g 都是线性l 可染的，则称g 是线性 七可选的g 的顶点列表色数是使得g 是线性k 可选的最小整数k ，用l c ( g ) 表 示他们获得了下面一些结论： 定理1 1 【2 8 】若g 是最大度为a 的树，则l c ( g ) = 会 + 1 定理1 2 设g = ，n 为完全二部图若m n ，则l c ( g ) = t c ( c ) = i l i f t + n 若图g 的任意子图都有k - 点，则称g 是七退化的 定理1 3 若g 是一个最大度为的2 - 退化图，则l c ( g ) a + 2 定理1 4 对一个a 3 的图g ，有l c ( g ) 5 定理1 5 对一个as4 的图g ，有l c ( g ) 9 定理1 6 对一个最大度为的外平而图g ，有f c ( g ) 今 + 2 ， 1 绪论 定理1 7 设g 是一个最大度为的平面图 ( 1 ) 若9 ( c ) 1 6 且23 ，则l c ( g ) 会1 + 1 ( 2 ) 若g ( c ) 1 0 ，则l c ( c ) f 会 + 2 ( 3 ) 若g ( c ) 8 ，则l c ( c ) f 今1 + 3 定理1 8 设g 是平面图且9 ，则l c ( g ) + 2 6 他们也给出了下面的猜想： 猜想1 1 【2 8 】若g 满足3 且不同构于k 3 ，3 ，则l c ( g ) 4 显然，l c ( c ) r 垒( 2 盟1 + 1 那么哪些图可以取到这个下界呢? r a s p a u d 和 w 抽g 例得到了下面的结论： 定理1 91 2 9 】对于一个平面图g ，如果存在( ，g ) ( 1 3 ，7 ) ，( 7 ，9 ) ，( 5 ，1 1 ) ，( 3 ，1 3 ) ) 满足a ( g ) a 且g ( g ) 玑那么i c ( g ) = r 垒衄21 j + 1 w a n g 和“删推广和改进了上面定理1 9 中的结果，他们证明了下面结果： 定理1 1 0 例设g 是一个可嵌入到有非负欧拉特征的曲面上的图若存在 ( ，g ) ( 1 3 ，7 ) ，( 9 ，8 ) ，( 7 ，9 ) ，( 5 ，1 0 ) ，( 3 ，1 3 ) 满足a ( c ) 且g ( g ) 夕，那么 i c ( g ) = r 蛔2 j + 1 易见，并不是所有的图都能够取到下界的如圈的线性色数为3 = 会 + 2 因 此自然会考虑对一些图类给出线性色数的上界，使其尽可能接近下界z x ( ，g ) 1 + 1 r a s p a u d ，w a n g 和l i ，3 1 ，3 2 】在这方面开展了大量研究，他们证明了： 定理1 1 1 例设g 是一个最大度为的平面图，有 ( 1 ) g ( g ) 6 ，则l c ( g ) 会1 + 4 ( 2 ) g ( g ) 5 ，则l c ( c ) 令 + 1 4 定理1 1 2 【3 1 】设g 是最大度为的图， ( 1 ) 则l c ( c ) 互1 ( 2 + ) ( 2 ) 如果4 ，则l c ( g ) 8 ( 3 ) 如果5 ，则l c ( g ) 1 4 定理1 1 3 【3 l 】设g 是最大度为的平面图且5 2 ，则i c ( c ) 等 + 5 定理1 1 4 3 2 1 设g 是最大度为a 不含4 圈的平面图，则l c ( c ) 今 + 8 3 1 绪论 1 3 本文的主要工作 本学位论文主要是对平面图类展开研究 第二章我们得到了下面的结论： ( 1 ) 对一个平面图g ，若a 6 ，则l c ( g ) 2 a + 1 ；若a 7 ，则l c ( c ) 2 a 第三章我们证明了下面的结果： ( 2 ) 若g 是一个g ( a ) 6 的平面图，则l c ( g ) 今1 + 3 ；且当a 薯 4 ，5 ，1 2 时，有l c ( g ) 会 + 2 第四章我们获得了下面的结果： ( 3 ) 若g 是一个g ( a ) 5 的平面图，则l c ( g ) 今 + 5 ；且当a 岳 7 ，8 ，1 4 ) 时，有l c ( g ) f 会 + 4 第五章我们获得了下面的结果： ( 4 ) 若g 是g ( a ) 4 的平面图，则l c ( g ) 等1 + 2 4 2 平面图线性色数的一个上界 在开始本章之前，先介绍本学位论文证明所用的方法和常用的记号本文的 证明应用经典的权转移方法首先，对于正整数m ，n ，记f = 2 ( m + n ) ，结合欧拉 公式i y ( g ) i i e ( g ) i + i f ( g ) j = 2 和 d ( ) = d ( ，) = 2 i e ( g ) i ， y ( g ) l f ( a ) 可以得到下面的恒等式： ( r o d ( u ) 一z ) + ( n d ( ，) 一z ) = - 2 1 盯y ( g )i e f ( g ) ( 木) 。定义初始权函数叫：对v v ( g ) 令w ( v ) = m d ( v ) 一z ；对，f ( g ) 令 w ( ) = n d ( f ) 一z 由公式( 木) 得总的权和为一2 f 然后定义一个权转移规则并且在 所有点和面上执行它一旦权转移结束，就会产生一个新的权函数在整个权 转移过程中权和是不变的，但是对于所有的z v ( a ) uf ( g ) ，有w 0 ) 0 这导 致了下面一个很明显的矛盾： 0 ( z ) = 彬( z ) = - 2 1 2 a ( g ) + 1 = 1 1 ，但对于任意的一个阶 数更小的平面图日，满足a ( h ) a ( a ) = 5 ，有i c ( h ) i i 容易看到g 是连通 的设c = l ，2 ，1 1 表示被应用的颜色集合 断言16 ( g ) 4 证明：假设g 包含1 点 与某点让相邻令h = g 一口，则日是一个平面图 满足a ( h ) sa ( g ) 5 由g 的极小性，日有一个线性染色c 应用颜色集合 c 为将c 扩充到整个图g ，我们用不在q ( 钍) u c ( 仳) ) 中的颜色染 因为 i c 。( u ) l t - 血p j = 【竿j 【垒i 乒j = 竽 一i = 2 ，总有一种颜色可以染 给 但这与g 的选择矛盾! 假设g 包含一个2 点u ，其邻点为z ，y 由g 的极小性知h = g 一 有一个 线性染色c 应用颜色集合c 我们用不在 c ( z ) ，c ) ) u 四( 0 ) u 蜥( ) ) 中的 颜色染秒 的禁用颜色数最多为a ( a ) + 1 = 6 ，于是我们可以用c 中的颜色染 好 这与g 的选择矛盾! 假设g 包含一个3 点秒，其邻点为z ，y ，z 由g 的极小性知日= g 一 ”+ z 可 ( 若z 可不存在) 有一个线性染色c 应用颜色集合c 我们用不在 6 2 平而图线性色数的一个卜界 c ) ，c ( 秒) ，c ( 名) u q ( ( g ( z ) u n c ( y ) u n c ( z ) ) 秒 ) 中的颜色染秒v 的禁用颜 色数最多为9 ，于是我们可以用c 中的颜色染好v 这与g 的选择矛盾! 断言1 证 完 断言2 一个5 点至多和两个3 一面相关联 证明：假设g 有个5 点 和超过两个的3 面相关联，则其中一定有两个3 面 是有公共边的仇“= 1 ，2 ，3 ，4 ，5 ) 是秒的邻点，五是和v 关联的面设 = 【v l u v 2 ， 2 = k 3 】，它们有公共边i v 2 ，如图2 1 ( a ) 所示令h = g 一钞- 4 - 秒1 诒，u 4 u 5 ( 若 v l v 3 或v 4 v 5 不存在) ，如图2 1 ( b ) 所示 ( a ) 图2 1 断言2 中的子结构 - ，。i - i ( b ) 由g 的极小性知日有一个线性染色c 应用颜色集合c 易见c ( v 4 ) c ( 奶) 且c ( v 1 ) ，c ( 晚) ，c ( v 3 ) 互不相同于是在 口l ，v 2 ，1 ) 3 ，v 4 ，v s 中至多有两个顶点染相同 颜色我们考虑下面两种情形： 情形1d ( ) = 3 或d ( f 5 ) = 3 不失一般性，假设d ( f 3 ) = 3 ，即u 3 v 4 e ( g ) 考虑下面两种情形： ( 1 1 ) c ( v 1 ) ，c ( 忱) ，c ( 地) ，c ( v 4 ) ，c ( ) 互不相同 假设c ( v i ) = i ( i = 1 ，2 ，3 ，4 ，5 ) 因为a ( g ) 5 ，所以i n g ( v 1 ) t ，v 2 i 3 ， i n g ( v 2 ) 钉，u 1 ，v 3 i 2 ，i g ( 地) 可，v 2 ，啦) i 2 ，i g ( m ) 秒，i 3 ， i g ( 5 ) 秒) i 4 易见i g ( i g ( v 1 ) 口，也 ) i 1 ，i g ( n g ( v 2 ) v ， u 1 ，忱 ) i 1 ，i g ( n o ( v 3 ) v ，v 2 ，u 4 ) i 1 ，i q ( g ( 砒) v ，) i 1 且i q ( g ( ) 7 、“致 一 2 平而图线性色数的一个卜界 ) i 2 于是i q ( g ( u - ) u ，忱) q ( n g ( v 2 ) u ，v l ，u 3 ，) i + | g ( n o ( v 3 ) v ，t j 2 ，v , ) l - + - i q ( g ( m ) ，v 3 ) l + l q ( g ( 佻) u ) ) l 6 如果l q ( g ( 秒1 ) ，t j 2 ) ) i + i q ( g ( 忱) 钉，v l ，v 3 ) l + l q ( g ( 3 ) 口，v 2 ，魄 ) i + i g ( n o ( v 4 ) v ，可3 ) ) i + i 四( n o ( v 5 ) ) ) i 在( n g ( v 1 ) 1 3 ，但对于任意的一个阶数更小的平面图日，满足 a ( l r ) 6 ，有i c ( h ) 1 3 设c = 1 ，2 ，1 3 表示被应用的颜色集合 断言1 6 ( g ) 5 证明：类似于定理2 1 中断言1 的证明可证6 ( g ) 4 假设g 包含一个4 点仉 且 3 1 ， 0 2 ，v a ，v 4 是口的邻点h = g t ，+ 0 1 0 2 ， 0 3 0 4 ( 若 0 1 0 2 或v a v 4 不存在) ， 如图2 3 所示由g 的极小性知日有一个线性染色c 应用颜色集合c 显然 c ( v 1 ) c ( v 2 ) 且c ( v s ) c ( 魄) ，考虑三种情形染u 图2 3 断言1 7 中的子结构 1 2 2 平而图线性色数的一个卜界 情形1u 1 ，u 2 ，u 3 ， 4 染互不相同的颜色 我们用不在 c ( 移1 ) ，c c v 2 ) ，c ( 口3 ) ，c ( 口4 ) u q ( n g ( v 1 ) ，) u g ( n o ( v 2 ) u ) ) u q ( g ( 地) 秒 ) u q ( n g c v 4 ) u ) 中的颜色染 秒的禁用颜色数最多为 4 + 【掣j + 【掣j + 【掣j + 【掣j 1 2 ，于是我们可以用c 中的 颜色染好秒 情形2 l ，u 2 ，u 3 ，u 4 恰有一对顶点染相同的颜色 不失一般性，设c ( v 1 ) = c ( 讥) 我们用不在 c ( u t ) ，c 沁) ，c ) uq ( n g ( v 1 ) u i v a c v a ) 口) ) uq ( g ( 抛) u ) ) ug ( n c c v 3 ) ) ) 中的颜色染t ，口的禁用颜 色数最多为1 2 。于是我们可以用c 中的颜色染好u 情形3 l ，v 2 ，秽3 ，u 4 有两对顶点染相同的颜色 不失一般性，设c ( v 1 ) = c ( 讥) 且c ( v 2 ) = c c v 3 ) 我们用不在 c ( 口1 ) ，c ( 耽) ，u g ( g ) u ( g ( 啦) t ，) ) uq ( n g c v 2 ) un o ( v 3 ) ) 中的颜色染t ， 的禁用 颜色数最多为1 2 ，于是我们可以用c 中的颜色染好 断言1 证毕 断言2 ，不存在一个坏5 点 证明：假设g 有一个坏5 点秒，则口至少和四个3 一面关联设v i ( i = 1 ，2 ，3 ，4 ，5 ) 是 的邻点， 是和口关联的面设 = v l v 忱l ，2 = 【v 2 v 秒3 ，h = 可m 】， h = h 伽吐h = g 一秒+ 沈蛳， 1 v 5 ( 若耽蛳或1 1 t ，5 不存在) ，如图2 4 所示 图2 4 断言2 7 中的子结构 由g 的极小性知日有一个线性染色c 应用颜色集合c 易见c ( v 1 ) c ( 耽) ， c ( v 1 ) c ( 佻) ，c ( v 4 ) c ( v 5 ) 且c ( t j 2 ) ，c c v 3 ) ，c ( v 4 ) 互不相同于是在 秒l ，v 2 ，地，v 4 ，口5 ) 1 3 2 平而图线性色数的一个卜界 中至多有两个顶点染相同颜色我们考虑下面两种情形： 情形1c ( v 1 ) ，c ( 现) ，c ( v 3 ) ，c ( v 4 ) ，c ( v 5 ) 互不相同 我们用不在 c ( 口1 ) ，c ( 忱) ，c ( ) ，c ( 啦) ，c ( 坞) ) ，q ( g ( 秽1 ) i ，忱) ) ，q ( n g ( v 2 ) 秒，v l ，珊 ) ，g 葛( g ( u 3 ) ，v 2 ，吼) ) ，四( g ( 地) u ，v 3 ，佻 ) ，q ( g ( ) t ，v 4 ) 中的颜色染口u 的禁用颜色数最多为1 2 ，于是我们可以用c 中的颜色染好u 情形2c ( 秽1 ) ，c ( v 2 ) ，c ) ，c ( 秒4 ) ，c ( v 5 ) 中有相同颜色 ( 2 1 ) c ( v 1 ) = c ( v 4 ) 或c ( 忱) = c ( v s ) 不失一般性，设c ( v 1 ) = c ( v 4 ) ，我们用不在 c ( 1 ) ，c ( 耽) ，c ( 地) ，c ( ) ) ，q ( ( g ( 忱) 秒，口1 ， ) u ( g ( ) t ， 0 2 ，魄 ) u ( g ( 地) t ，啦，) ) 和g ( ( g 0 1 ) ，v 2 ) u ( n g ( i j 4 ) ， 3 ，移5 ) ) 中的颜色染t ，u 的禁用颜色数至多为1 2 ，我们可以用c 中的颜 色染好钉 ( 2 2 ) c ( v 1 ) = c ( v 3 ) 或c ( 地) = c ( v 5 ) 不失一般性，设c ( v 1 ) = c ( v 3 ) ，我们用不在 c ( ，) ，c ( 秒2 ) ，c ( 魄) ，c ( ) ) ，q ( ( g ( 忱) ， 1 1 1 ，忱】) u ( g ( 讥) ， v 3 ，佻 u ( g ( ) ，蛳) ) ) 和q ( ( g ( t ，1 ) ，忱 ) u ( g ( v 3 ) u ， , 2 ，讥) ) ) 中的颜色染t ，u 的禁用颜色数至多为1 2 ，我们可以用c 中的颜 色染好郇断言2 证毕 为了推出矛盾，我们仍应用变形的欧拉公式( 木) ，取m = 1 ，n = 2 定义初始 权函数叫：对钉v ( c ) 令w ( v ) = d ( v ) 一6 ；对，f ( g ) 令w ( f ) = 2 d ( f ) 一6 定 义权转移规则如下： ( r 2 1 ) 设，是一个4 + 一面，口是，边界上的一个5 点当秽在，上每出现一次时， ，给秒权石1 设为权转移结束后的新权函数令u y ( g ) ，由断言1 7 ，g 不含4 一点，于 是d ( v ) 5 如果d ( v ) = 6 ，伽( 口) = w ( v ) = d ( v ) 一6 = 0 如果d ( 口) = 5 ，由断言 2 ， 至少和两个4 + 面 ，如关联注意到，当g 含有割点时， 和五是可以重合 成一个而的由( r 2 1 ) ， 和止分别给u 权互1 ，因此，埘( ) w ( v ) - i - 2x = 0 1 4 2 平面图线性色数的一个卜界 令f f ( g ) 如果d ( ，) 4 ，由( r 2 1 ) ，w 7 ( ，) w ( f ) 一d ( ，) x = d ( ，) x 一6 0 如果d ( ，) = 3 ，w ( ，) = ( ，) = 0 至此，我们证明了所有的叫7 ( z ) 之0 0 v ( c ) uf ( g ) ) 定理2 2 证毕 2 2 7 的情形 定理2 3 若g 是a ( g ) = 7 的平面图，则l c ( g ) 1 4 证明：应用反证法假设定理不成立设g 是一个极小反例，即g 是一个平面 图满足a ( a ) = 7 且i c ( g ) 1 4 ，但对于任意的一个阶数更小的平面图日，满足 ( 日) a ( g ) = 7 ，有l c ( h ) 1 4 设c = 1 ，2 ，1 4 表示被应用的颜色集合 类似于定理2 1 中断言l 的证明可证6 ( g ) 4 断言1 4 点至多关联一个3 面 证明：假设g 有一个4 - 点u 至少和两个3 一面关联设他( i = 1 ，2 ，3 ，4 ) 是t ，的 邻点，五是和 关联的面， = v l v v 2 令h = g t ，4 - v , v 4 ( 若v 3 v 4 不存 在) ，由g 的极小性知日有一个线性染色c 应用颜色集合c 易见c ( v 1 ) c ( 晚) ， c ( v 3 ) c ( v 4 ) 于是在v l ，v 2 ，v 3 ，弛) 中至多有两个顶点染相同颜色我们考虑下 面两种情形： 情形1d ( 厶) = 3 或d ( f 4 ) = 3 即秒关联两相邻3 - 面，不失一般性，设d ( 厶) = 3 ，v 2 v 3 e ( g ) 考虑下面两种 情形： ( 1 1 ) c ( v 1 ) ，c ( 耽) ，c ( 哟) ，c ( 啦) 互不相同 我们用不在 c ( u 1 ) ，c ( 耽) ，c ( 地) ，c ( v 4 ) u c ；：( g ( 1 ) 秒，忱) ) u g ( g ( 睨) 秒，v l ， v 3 ) u c l ( n g ( v 3 ) 秒，v 2 ) u c l ( n g ( v 4 ) u ) ) 中的颜色染口 1 3 的禁用颜色数最多 为4 + 【学j4 - 【掣j + 【学j + 【学j = 1 3 ，于是我们可以用c 中 的颜色。染好u 1 5 2 平而图线性色数的一个卜界 ( 1 2 ) c ( v 1 ) ，c ( 忱) ，c ( v 3 ) ，c ( v 4 ) 中有相同颜色 我们用不在 c ( 1 ) ，c ( 忱) ，c ( ) ，c ( v 4 ) u c i ( ( g ( 1 ) u ，v 2 ) u ( n a ( 郇2 ) ，v l ， 地 ) u ( g ( ”3 ) 口，v 2 ) u ( g ( 魄) ，) ) 中的颜色染t ，i c ( 口1 ) ，c ( 秽2 ) ，c ( 砚) ，c ( 啦) i 3 ，i q ( ( n c ( 秒t ) ，抛，) u ( g ( 忱) ，v l ，忱) ) u ( g ( 口3 ) 移，v 2 ) u ( g ( 砒) ) ) i 1 0 ，所以 的禁用颜色数最多为1 3 ，于是我们可以用c 中的颜色染好口 情形2d ( ) = 3 关联两不相邻3 面，v 3 v 4 e ( g ) 考虑下面两种情形： ( 2 1 ) c ( 口1 ) ，c ( 忱) ，c ( 忱) ，c ( v 4 ) 互不相同 我们用不在 c ( u 1 ) ，c ( 现) ，c ( u 3 ) ，c ( 蛳) ) u g ( g ( u ) t ，咙 ) u q ( g ( 吨) t ， 1 ) u g ( n g ( v 3 ) u ，v , i ) u c ；( n g ( v 4 ) 秒，v 3 ) 中的颜色染口口的禁用颜色数最 多为4 + 【竿j4 - 【学j4 - 【学j + 【学j = 1 2 ，于是我们可以用c 中的颜色染好口 ( 2 2 ) c ( v 1 ) ，c ( v 2 ) ，c ( u 3 ) ，c ( v 4 ) 中有相同颜色 我们用不在 c ( 1 ) ，c ( 忱) ，c ( v 3 ) ，c ( 砒) ，u q ( ( g ( 钉1 ) t ，砚) ) u ( g ( t j 2 ) u ，秒l ) u ( g ( u 3 ) 钞，m ) ) u ( n g ( 地) u ，u 3 ) ) 中的颜色染u i c ( u 1 ) ，c ( 忱) ，c ( 地) ，c ( 啦) ) i 3 ，i c 苫( ( k ( 1 ) 钞，忱 ) u ( k ( 耽) ，v l i ) u ( n g ( u 3 ) v ，v 4 ) u ( 7 g ( 4 ) u ，地 ) ) i 1 0 ，所以钞的禁用颜色数最多为1 3 ，于是我们可以用c 中的颜色染好口断言 1 证毕 断言2 ，类型1 的4 点的两个不关联3 面的邻点一定是6 + 点 证明：假设g 有一个类型l 的4 点钞，u 有一邻点为不关联3 面的5 一点设 u i ( i = 1 ，2 ，3 ，4 ) 是 的邻点， 是和钞关联的面， = v l v v 2 ，d ( v 3 ) 5 令 h = g 一 - 4 - v 3 v , ( 若v a v a 不存在) 由g 的极小性知日有一个线性染色c 应 用颜色集合c 易见c ( 移1 ) c ( 吨) ，c ( v 3 ) c ( 地) 于是在 口l ， 1 1 2 ，地，v 4 中至多有 两个顶点染相同颜色我们考虑下面两种情形： 情形1c ( v 1 ) ，c ( 忱) ，c ( 哟) ，c ( v 4 ) 互不相同 1 6 2 平而图线性色数的一个卜界 我们用不在 c ( 饥) ，c ( 秽2 ) ，c ( 3 ) ，c ( 蛳) ) u q ( g ( u 1 ) “忱 ) u q ( g ( 现) ， u 1 ) u 四( n c ( v 3 ) u ) u g ( n a ( v 4 ) 秒 ) 中的颜色染u 秒的禁用颜色数最多为 4 + 【竿j - i - 【学j - i - 【掣j - i - 【掣j 4 + 【等j + 【等j + 【学j + l 孕l = 1 3 ，于是我们可以用c 中的颜色染好u 情形2c ( v 1 ) ，c ( 现) ，c ( 吨) ，c ( v 4 ) 中有相同颜色 我们用不在 c ( t ，- ) ，c ( 耽) ，c ( 3 ) ，c h ) u 铝( ( g ( 秽1 ) 秒，忱) ) u ( g ( 忱) ，u 1 ，) u ( g ( 忱) 移) ) u ( n g ( v t ) ) ) 中的颜色染u i c ( 秒1 ) ，c ( 砚) ，c ( v 3 ) ，c ( 啦) i 3 ， i g ( ( g ( 秒1 ) 钉，v 2 ) u ( n g ( v 2 ) ， 1 ) ) u ( g ( 地) ) u ( g ( 砒) 口，) ) i 1 0 ， 所以u 的禁用颜色数最多为1 3 ，于是我们可以用c 中的颜色染好t ，断言2 ”证 毕 断言3 类型5 的5 点至多和一个6 一点相邻 证明：假设g 有一个类型5 的5 点u ，则口和五个3 面关联对i = l ，2 ，3 ，4 ，5 ， 设u i 是口的邻点，五是和口关联的面，中至少有两个为6 一点设 = 【u i v v 2 ， ，2 = 【u 2 u u 3 ，f 3 = 【v 3 v v 4 ， = v , v v s ， = v s v v i 令h = g t ，- t - 忱奶 ( 若 抛不存在) ，由g 的极小性知日有一个线性染色c 应用颜色集合c 易见 c ( v 2 ) c ( v 3 ) ，c ( v a ) c ( v 4 ) ，c ( 地) c ( v 5 ) 且c ( u 1 ) ，c ( 忱) ，c ( v 5 ) 互不相同于是在 口l ，t j 2 ，地，v 4 ，v s 中至多有两个顶点染相同颜色我们考虑下面两种情形： 情形1c ( 秒1 ) ，c ( v 2 ) ，c ( 地) ，c ( 魄) ，c ( v 5 ) 互不相同 我们用不在 c ( 口1 ) ，c 池) ，c ( 地) ，c ( 弛) ，c ( 5 ) ，u q ( g ( 秒) ，v 2 ，v s ) u 四( g ( u 2 ) 秽，u 1 ，v 3 ) u 四( g ( 铅) v ，v 2 ，v 4 ) u q ( n g ( v 4 ) v ，v s ，v s ) u g ( n g ( v 5 ) 移，魄，v l ) 中的颜色染 i c ( 秒1 ) ，c ( t j 2 ) ，c ( 珊) ，c 似) ，c ( ) i + i 四( g ( 1 ) ，也，鸭) ) + i c 蔷( g ( 忱) 秒， 0 1 ，地) ) i + i q ( n g ( v 3 ) v ，忱，u 4 ) i + i c 譬( g ( ) 秒，地，) ) i + i c 薹( n g ( v 5 ) v ，呲，v l ) l 5 + 【譬j + 【譬