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

摘要 图的线性染色 摘要 用g = ( ve ) 表示一个顶点集为y ，边集为e 的有限、简单无向 图， 1 ，2 ，七) 表示k 个颜色的集合g 的一个正常知- 染色是一个映射： y 一( 1 ，2 ，七) 使得相邻的顶点接受不同的色如果g 有一个正常七染色， 则称g 是后一可染的g 的色数x ( a ) 是使得g 是正常后一可染的最小的非负整 数七如果图g 的一个正常染色满足染任意两种颜色的顶点集合导出的子图是 一些点不交的路的并，则称这个正常染色为图g 的线性染色图g 的线性色数用 i c ( g ) 表示，是指g 的所有线性染色中所用的最少颜色的个数 1 9 9 8 年，y u s t e r t l 】首先研究了图的线性染色证明了任意图g 的线性色数满 足l c ( g ) = 0 ( i ) ，且构造出了一类图使得l c ( g ) = q ( ) 事实上，这个概念是 图的无罔染色的一种特殊情形无圈染色的概念是由g r f i n b a u m t 2 l 提出的，图g 的一个无圈染色是g 的一个正常染色，使得染任意两种颜色的顶点集合导出的 子图是一个森林 本学位论文主要是对前人的一些研究结果的改进和扩充，对非负特征图、平 面图和一些度数较小的图的的研究设a ( g ) 和g ( a ) 分别表示图g 的最大度和 围长 在第一章中，我们给出本文所用到的基本概念，简述了相关领域的研究现状 以及呈现了本文的主要结果 在第二章中，我们证明了下面的结果： ( 1 ) 对于每一个非负特征图g ，若存在一个有序对( a ，g ) ( 1 3 ，7 ) ，( 9 ，8 ) ， 一t 一 摘要 ( 7 ，9 ) ，( 5 ，l o ) ，( 3 ，1 3 ) ) 使得( g ) 2 且夕( g ) 2g ，则i t ( g ) = 全笋 + 1 在第三章中，我们获得了下而的结果： ( 1 ) 对于每一个平面图g ，若满足a ( g ) 3 且g ( c ) 1 2 或者( g ) 7 且夕( g ) 8 ，则l c ( e ) = 垒笋1 + 1 在第四章中，我们又对度数较小的图进行了研究，得到了下面两个结果： ( 1 ) 若图g 的最大度为4 ，则i c ( g ) 8 ( 2 ) 若图g 的最大度为5 ，则l c ( g ) 1 4 关键词：线性染色；非负特征图；围长：最大度 一i i a b s t r a ( 了r l l n e a rc o l o r i n g o fg 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 to fv e r t i c e sv a n dt h es e to f e 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 - c o l o r i n go f gi sam a p p i n gf r o mv t ogs u c ht 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 fg h a sap r o p e rk - 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 ci n d e x ，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 r 后s u c ht h a tg i sk - c o l o r a b l e ap r o p e rv e r t e x c o l o r i n go fag r a p hg i sl i n e a ri ft h eg r a p hi n d u c e db yt h ev e r t i c e so fa n yt w oc o l o r c 1 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 rl c ( g ) o ft h e g r a p hg i 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 rc o l o r i n go fg i n1 9 9 8 ，y u s t e r 1 】f i r s ti n v e s t i g a t e dt h el i n e a rc o l o r i n go f g r a p h sb ys h o w i n gl c ( g ) = 0 ( 2 ) f o ra n yg r a p hg a n dc o n s t r u c t i n gag r a p hgs u c ht h a tl c ( c ) = q ( i ) i n d e e d ， t h i sc o n c e p ti sas p e c i a lc a s eo fa c y c l i cc o l o r i n go fg t h ea c y c l i cc o l o r i n go fgw a s i n t r o d u c e db yg r t i n b a u m t 2 1 ，ap r o p e rv e r t e xc o l o r i n go fgi sc a l l e da c y c l i ci fa n yt w o c o l o rc l a s s e si n d u c eaf o r e s t i nt h i sm a s t e rt h e s i s ，o u rt h e o r e m sa r ee x t e n s i o na n di m p r o v e m e n to ft h ep r e c e d e n t r e s u l t s ，a n di n v e s t i g a t et h eg r a p ho fn o n n e g a t i v ec h a r a c t e r i s t i c ，p l a n a rg r a p ha n dt h e g r a p hw i t hs m a l l e rm a x i m u md e g r e e 。w eu s e ( g ) a n do ( o ) 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 md e g r e ea n dg i r t ho fg 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 dg i v eac 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 一 i nc h a p t e r2 ，w ep r o v et h a t ： ( 1 ) e v e r yg r a p ho fn o n n e g a t i v ec h a r a c t e l i s t i cg h a sl c ( a ) = - - f 、l + 1i ft h e r e i sap a i r ( a ，9 ) ( 1 3 ，7 ) ，( 9 ，8 ) ，( 7 ，9 ) ，( 5 ，l o ) ，( 3 ，1 3 ) ) s u c ht h a tg s a t i s f i e s ( g ) a n dg ( a ) 9 i nc h a p t e r3 ，w eo b t a i nt h a t ： ( 1 ) e v e r yp l a n eg r a p hg h a sl c ( a ) = 垒笋 + li fg s a t i s f i e s ( g ) 3a n d g ( a ) 1 2 0 r ( g ) 7a n d g ( c ) 8 i nc h a p t e r4 ，w ei n v e s t i g a t es o m eg r a p h sw i t hs m a l l e rm a x i m u md e g r e e ，a n dw e o b t a i nt h a t ： ( 1 ) i fg i sag r a p hw i t h ( g ) 5 ，t h e nz c ( a ) s1 4 ( 2 ) i fg i sag r a p hw i t ha ( g ) 4 ，t h e ni c ( g ) 8 k e yw o r d s ：l i n e a rc o l o r i n g ；g r a p h o fn o n n e g a t i v ec h a r a c t e r i s t i c ；g i r t h ；m a x i m u m d e g r e e 一一 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 研究生签名：辱 超 学位论文使用授权声明 眦研护 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许论文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不同媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生签名：存垒 导师签名： 罗缈 日期： 即事删 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理 条例。我的学位论文中凡引用他人已经发表或未发表的成 果、数据、观点等，均已明确注明并详细列出有关文献的名 称、作者、年份、刊物名称和出版文献的出版机构、出版地和 版次等内容。论文中未注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ：并黟 指导教师：砀的 一、绪论 ( 一) 、基本概念 一、绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号 一个有序对g = ( ue ) 称为一个无向图，其中y 是一个有限集合，e 是y 中 的不同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图的 边通常用y ( g ) ，e ( g ) 分别表示图g 的顶点集合与边集合，用i v ( g ) i ，i e ( g ) 1 分 别表示g 的顶点数与边数没有重边和环的图叫做简单图除非特别指出，本文 研究的图均指有限简单无向图对于图g 中的顶点u 和u ，若边e = u v e ( g ) ， 则称牡和u 相邻，札和”互为邻点同时也称札和u 是e 的端点，1 1 , 和u 分别与 e 相关联若“( 或e ) 在面j f 的边界上，则说钍( 或e ) 与，在g 中相关联称有一 个公共端点的两条边相邻，以及至少有一条公共边的两个而相邻设u 是一个 顶点，与 相关联的边的条数叫做v 的度数，记作如( u ) 与u 相邻的顶点的全 体叫作口在图g 中的邻域，记作g ( u ) 度数为k ，至少为k ，或至多为k 的顶 点，我们称为七点，扩点，或k 一一点g 中顶点的度中最大者和最小者分别称为 g 的最大度和最小度，分别记作( g ) 和6 ( g ) 在不产生混淆的情况下，我们把 i v ( g ) i ，l e ( g ) i ，g ( u ) ，d g ( u ) ，( g ) ，6 ( g ) 分别简记为l y i ，l e l ，( u ) ，d ( u ) ，a ，6 如果能将图g 画在平面上，使得它的边仅在端点处才可能相交，则称图 g 是可平面化图图的这种平面上的画法称为图的平面嵌入，或称为平面图 设图g 是平面图，我们常用f ( g ) 表示面集合对于f f ( g ) ，用b ( y ) 来表示 面，的边界若，的边界点依顺时针方向排列为u l ，乱2 ，那么我们就记 ，= 心。u z 让扎】有时简记v ( f ) = y ( 6 ( ，) ) 把途径b ( f ) 的长度称为面，的度 一1 一 一、绪论 度数为七，至少为后，或至多为k 的而，我们称为舟一而，惫+ 一而，或k - _ 面若一个而 的边界是一个圈，则称这个面是一个简单面 本文所用术语和符号基本上与文献 3 中一致本节中未介绍的其他图论术 语将在必要时予以阐述 ( 二) 、 关于线性染色的研究现状 图染色问题的研究来源于著名的四色问题，即在平面上任何一张地图，总可 以用至多四种颜色给每一个国家染色，使得任何两个相邻国家( 公共边界上至少 有一段连续曲线) 的颜色是不同的关于平而图的染色问题是图论界的热点也是 难点图的染色理论也是图论中最重要的分支之一，在无线通讯频道分配、舰队 维护、任务分派、交通定向等诸多领域都有着广泛的应用，见文献【4 】 图g 的一个正常顶点染色是指k 种颜色l ，2 ，k 对于g 的各顶点的一个 分配，使得任意两个相邻的项点分配以不同颜色若图g 有一个正常奄点染色， 那么就称图g 是良点可染色的图g 的色数是指g 有一个正常k 顶点染色的数 k 的最小值，用x ( a ) 表示关于平而图顶点染色问题已经在【5 1 2 】得到了广泛的 研究， 1 9 9 8 年，y u s t e r 1 】首先提出并且研究了图的线性染色问题如果图g 的一个 正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并，则 称这个正常染色为图g 的线性染色图g 的线性色数用i c ( a ) 表示，是指g 的所 有线性染色中所用的最少颜色的个数同时，y u s t e r 证明了任意图g 的线性色数 满足l c ( a ) = o ( 2 ) ，且构造出了一类图使得i c ( a ) = q ( ) 事实上，这个概念 是图的无圈染色的一种特殊情形图g 的一个无圈染色是g 的一个正常染色， 使得染任意两种颜色的顶点集合导出的子图是一个森林无圈染色的概念是由 一2 一 一、绪论 g r i i n b a u m t 2 】提出的，而无圈染色已经在文献 1 3 - 2 1 r f l 广泛研究 最近，e s p e r e t ，m o n t a s s i e r 和r a s p a u d 冽把线性染色的概念推广到线性选择 性上来如果图g 的一个顶点色列表l 是一个颜色集合簇，它指定g 的每个顶 点u 一个颜色集合l ( 口) 若g 有一个线性染色7 r ，使得对每一个顶点v v ，有 丌( u ) 三( 口) ，则称g 为l 线性可染的或者称7 r 是g 的一个l 线性染色若对每 一个满足i l ( u ) l k ，u v 的l ，g 都是三一点可染的，则称g 是七一线性可选择的 g 的顶点列表色数是使得g 是七线性可选择的最小的非负整数庇，用z c ( g ) 表示 他们研究了树，格子图，完全二部图，平面图，外平面图，最大度为3 或4 的图以及 有较小最大平均度的图的线性选择数他们证明了下面一些定理： 定理1 i 【2 2 】设g 是一个平i l ；| 1 图 ( 1 ) 如果9 ( g ) 1 6 且( g ) 23 ，则2 7 c ( g ) 垒笋1 + 1 ( 2 ) 如果夕( g ) i 0 ，则f f c ( g ) 学 - i - 2 ( 2 ) 如果夕( g ) 8 ，则r c ( a ) 垒笋1 + 3 定理1 2 设g 是平面图且a ( c ) 9 ，则l c ( c ) a + 2 6 定理1 3 设g 是树且最大度为a ，则2 7 c ( g ) = 会+ 1 令一表示独立集分别为l v i = m 和i v 7 i = 扎的完全二部图他们得到了 下面的结果： 定理i 4 如果m 扎，则l c ( g ) = l c ( a ) = 号1 + 仡 如果对于图g 中的任意一个子图，都存在个七一点，则我们称g 是足退化 的 定理1 5 如果g 是一个最大度为的2 一退化图，则l c ( g ) a + 2 一气一 一、绪论 定理1 6 如果g 满足最大度a 3 ，则r c ( g ) 5 定理1 7 如果g 满足最大度4 ，则l c ( g ) 9 定理i 8 如果g 是一个最大度为a 的外平面图，则r c ( a ) 会 + 2 他们在文章中也给出了下面的猜想： 猜想1 1 2 2 1 如果g 满足最大度a 3 且不同构于娲，3 ，则l c ( g ) 4 a r a s p a u d 不f l w e i f a nw a n g 在这方面作了许多工作，他们证明了下面一些定 理： 定理1 9 设g 是平面图且( g ) 8 5 ，则l c ( g ) l 而9 a j + 5 定理1 1 0 设g 是不含四圈的平而图，则l c ( g ) 会 + 1 6 定理1 11 设g 是平而图 ( 1 ) 夕( g ) 6 ，则1 c ( g ) f 垒笋 + 4 ( 2 ) 夕( g ) 5 ，则l c ( g ) 垒笋1 + 1 4 易见，对于任意的图g 有l c ( a ) 竽 + 1 因此，我们很自然的就要去考 虑这样一个问题：哪些图可以达到这个下界昵? r a s p a u d 和w a n g t 2 3 】证明了下面结 果： 定理1 1 2 2 3 对于一个平面图g ，若存在一个有序对( a ，g ) ( 1 3 ，7 ) ，( 7 ，9 ) ，( 5 ，1 1 ) ， ( 3 ，1 3 ) ) 使得( g ) a 和夕( g ) g ，则l c ( g ) = 垒笋1 + 1 以上是关于线性染色以及线性选择性的一些已知结果与研究现状 ( 三) 、本文的主要工作 本学位论文主要是对定理1 1 2 的推广和扩充，对非负特征图类和平面图类 展开研究 一d 一 一、绪论 在第二章巾我们证明了下而的结果： ( 1 ) 对于每一非负特征图g ，若存在一个有序对( ，9 ) ( 1 3 ，7 ) ，( 9 ，8 ) ，( 7 ，9 ) ，( 5 ，1 0 ) ， ( 3 ，1 3 ) ) 使得( g ) 2 且9 ( g ) 9 ，则1 c ( g ) = i - z - - 、1 十1 在第三章中我们获得了下面的结果： ( 2 ) 对于每一个平面图g ，若满足( g ) 3 且e ( c ) 1 2 或者( g ) 7 且9 ( g ) 8 ，则i t ( e ) = r 鲻21 + 1 在第四章中，我们对最大度较小的图的线性色数进行t o 究，得到了下面两 个结论： ( 1 ) 若图g 的最大度为4 ，则l c ( g ) 8 ( 2 ) 若图g 的最大度为5 ，则l c ( g ) 1 4 一5 一 二、关于非负特征图的线性染色问题 二、关于非负特征图的线性染色问题 如果个图g 具有非负的欧拉特征，则称g 为非负特征图欧式平面，摄影 平面，圆环面，克莱因瓶都是具有非负欧拉特征的曲面对于一个非负特征图g ， 我们用r ( e ) 表示它的面集合任意的，f ( g ) ，用b ( f ) 来表示，的边界如果 仳l ，u 2 ，u n 是b ( f ) 上按顺时针方向的点，则记为f = “1 7 2 2 “。 ，注意到点的 重复出现是允许的面的度是指它的边界上边的条数，其中割边被计算两次对于 任意的x v ( c ) uf ( g ) ，用d e ( x ) 表示g 中z 的度在不产生混淆的情况下，可 以用简单的用d ( x ) 代替d a ( x ) 一个度为k 的顶点( 或而) 被称为七一点( 或k 一而) ， 我们用g ( 口) 来表示g 中移的邻点的集合在整篇论文中我们将非负特征图简 写为n c 一图 设g 是个n c 图，u y ( g ) 我们用n 2 ( v ) 表示与t 7 相邻的2 一点的个数 如果n 2 ( v ) = d ( u ) ，也就是说， 的所有邻点为2 一点，则称 为坏点设v 是一个 2 点，如果n 2 ( v ) 1 ，则称 为类型i ；如果u 正好和两个3 一点相邻，则称u 为类 型i i 设c 是g 的一个部分线性染色，颜色集合为c 对于任意的v y ( g ) ，我们 用q ( t ，) 来表示c 中正好在g ( u ) 上出现两次的颜色子集合这个记号将会在 下面的讨论中多次用到 为了完成证明定理2 1 的证明，我们证明下面一个更强的结果： 定理a 设m 是一个正整数，g 是一个n c 一图使得( g ) m 如果g 满足下列条件 之一，n l c ( e ) t m l + 1 ： ( 1 ) m 1 3 且9 ( g ) 7 ( 2 ) m 9 且9 ( g ) 8 一6 一 二、关于非负特征图的线性染色问题 ( 3 ) m 7 j | g ( g ) 9 ( 4 ) m 芝5 r g ( g ) 1 0 ( 5 ) m 3 且g ( v ) 1 3 证明：应用反证法假设定理不正确设g 是一个极小反例，即g 是一个满足假 设条件的n c 一图，l c ( g ) f 警1 + l ，但对于任意的一个阶数更小s j n c 一图日满足 和g 相同的m 和围长条件，则有i c ( h ) sf 等1 + 1 很容易看到g 是连通的接 下来我们证明6 ( g ) 2 假设g 包含1 点口与u 相邻令h = g u ，则日是一个n c 图且满足 a ( h ) a ( g ) 和g ( h ) = 9 ( g ) 由g 的极小性，日有一个线性染色c 应用 f 警 + 1 种颜色为了将c 扩充到整个g ，我们用不在q ( u ) u c ( “) ) 中的颜色染 口因为 i c ：( u ) l 【尘笋j = 【掣j 【垒嘎出j l - 生j = 等1 1 ， 总有一种颜色可以染给口但这与g 的选择矛盾! 在下面的证明中我们应用权转移的方法首先，根据围长的要求选择一个合 适的整数k 2 结合n c 图上的欧拉公式 i y ( g ) j l e ( g ) l + l f ( g ) i 0 和 ed ( v ) = d ( f ) = 2 1 e ( g ) ， , , ev c c ) l e e ( g ) 我们可以得到下面一个不等式： u y ( g ) ( 尼一2 ) d ( 口) 一2 k 】+ ，f ( g ) ( 2 d ( ，) 一2 七) 0 ( 2 1 ) 在v ( c ) uf ( g ) 上定义权函数w ，对于u y ( c ) 令叫( u ) = ( k 一2 ) d ( u ) 一2 k ， 对于，f ( g ) 令叫( ，) = 2 d ( ) 一2 七总的权和是非正数然后我们定义一系列的 一7 一 二、关于非负特征图的线性染色问题 权转移函数w 7 在整个权转移过程中权和都是不变的，但是w 7 满足下面性质( i ) ( i ) 对于所有的z v ( g ) uf ( g ) ，有叫7 ( z ) o ； ( i i ) 存在某个x + v ( g ) uf ( g ) 使得w ( x + ) 0 0 w 7 ( z ) =w ( x ) 0 在下面的的证明中，我们简单记k = 警 - i - 1 ，用c = 1 ，2 ，k ) 表示k 断言a 假设i c i = k = 等 + 1 设z 是一个2 一点，乱，钉为z 的邻点且 如( u ) d g ( 札) 如果2 d c ( u ) 4 ，则l 华j + d g ( u ) k i en ：假设l 华j + d g ( ) k 一1 设u 1 ，u 2 ，；是u 的不i nt - - z 的邻 点，其中m = d a ( v ) 一1 设日= g z 则h 是一个n c 一图且满足i h i j g l ， a ( h ) a ( g ) m ，g ( h ) 9 ( g ) 由g 的极小性可知，h 有一个线性染色c l ( z ) ： c ( q ( 札) u c ( u ) c ( u 1 ) c ( m ) ) ) i ，c ( u ) = c ( u ) ic ( 岛( u ) u c ( u ) ，c ( u ) ，c ( u - ) ，c ( u 。一) ) ) i fc ( u ) c ( u ) i c = ( u ) l l 生笋j = l 学j k 一1 一d c ( u ) ， j 上( z ) j l c i l q ( u ) j m l k 一( k 一1 一d e ( v ) ) 一d a ( v ) = 1 二、关于非负特征图的线性染色问题 因此，可用l ( x ) 巾的一个颜色染z ，从而将c 扩充到整个g ，矛盾于g 的选 择断言a 证毕! 第1 部分m 1 3 且g ( a ) 7 n i c i = k = 譬1 + 1 8 1 1 1 断言a ，我们有： 断言1 1 设一个2 一点x 和两个点v ，u 相邻且d ( u ) d ( 札) 如果2 d ( v ) s4 ，则 l 下4 ( - , ) - 1 j + d ( ”) 8 从断言1 1 立即可以得到下面一个推论： 观察1 1 设一个2 一点x 和两个点口，u 相邻且d ( v ) d ( 乱) ( 1 ) 如果d ( v ) = 2 ，则d ( u ) 1 3 ( 2 ) 如果d ( v ) = 3 ，则d ( u ) 1 1 ( 3 ) 如果d ( v ) = 4 ，则d ( u ) 9 我们令等式( 聿) 中k = 7 定义一个初始权函数：如果 y ( g ) ，则w ( v ) = 5 d ( v ) 一1 4 ，如果，f ( g ) ，则w ( f ) = 2 d ( f ) 一1 4 在给出权转移规则之前我们引 进一个概念 设点v 满足d ( u ) 21 4 或d ( v ) = 1 3 且n 2 ( v ) o ) ( r 1 3 ) 如果4 d ( v ) 1 2 ，则u 转( w ( v ) 一；) d ( t ，) 给每一个相邻2 一点 ( r 1 4 ) 每一个3 - 点转丽1 3 1 给每一个相邻的2 一点 ( r 1 5 ) 每一个d ( f ) 8 的面，转l 给b ( f ) 中每一个相邻于两个类型i2 一点 的坏1 3 一点 很容易从( r 1 i ) 至i j ( r 1 4 ) 得到下面的观察： 观察1 2 设v 是一个度数大于等r 丁3 的点，u 是与u 相邻的一个2 点 ( 1 ) 如果d ( v ) 1 3 ，则u 给 2 至少竽； ( 2 ) 如果1 1 d ( v ) 1 2 ，则u 给让至少弦8 1 ， ( 3 ) 如果d ( u ) 9 ，则u 给让至少两6 1 ， ( 4 ) 如果d ( v ) 5 ，则u 给札至少面2 1 ， ( 5 ) 如果d ( v ) = 4 ，则u 给u 至少警 设w 7 为权转移结束后的新权函数我们来验证对于所有的：7 2 v ( a ) uf ( g ) 有训7 ( z ) o ，且存在某个z + v ( a ) uf ( g ) 使得w 7 ( z + ) 0 设f f ( g ) 因为g ( g ) 7 ，所以d ( ，) 7 如果d ( f ) = 7 ，则易得 w 7 ( ，) = w ( f ) = 0 如果d ( f ) = 8 ，则f 最多关联两个与b ( f ) 上两个类型i2 一点相邻的坏1 3 点 因此，由( r 1 5 ) 可知： 伽7 ( ，) w ( f ) 一2x1 = 2 8 1 4 2 = 0 一1 n 一 二、关于非负特征图的线性染色问题 如果d ( ，) 9 ，则f 最多关联【挈j 个与b ( 厂) 上两个类型1 2 一点相邻的坏 1 3 一点因此，由( r 1 5 ) 可知： 叫7 ( ，) 牡，( ，) 一【竽j22 d ( f ) 一1 4 一 d ( ，) = ；d ( ，) 一1 4 1 设v y ( g ) 因为6 ( c ) 2 ，所以d ( v ) 2 假设d ) 1 4 如果d ( 铷) 1 5 或d ( u ) = 1 4 且n , 2 ( u ) 5 d ( z k ) - 1 4 - 4 ( d ( z k ) - 2 ) - i 二d ( z k ) - - 2 1 ，一 二、芡于爿 负特征图的线性染色问题 = 1 一赫 甍 因此 w 7 ( 钉) 5 1 + a ( z 2 ) + 盯( 2 3 ) 一4 n 2 ( v ) 25 1 + 2 夏1 3 4x1 3 = 矗 到现在为止我们证明了w 7 满足性质( i ) 假设w 7 不满足性质( i i ) ，也就是说，对于所有的z v ( a ) uf ( g ) ，有 w 7 ( z ) = 0 成立则根据先前的证明我们可以看到：对于所有的厂f ( g ) ，必有 d ( f ) 7 ，8 ) ；对于所有的v y ( g ) ，必有d ( v ) 0 ，且对所有的z f ( g ) ，有 w 7 0 ) 0 因此，( i ) 和( ) 成立证毕! 第3 部分m 7 且g ( a ) 9 则j c i = k = f 丁m 1 + 1 5 由断言a ，我们有： 断言3 1 设一个2 一点z 和两个点v , u 相邻且d ( 口) d ( u ) 如果2 d ( v ) 3 ，则 i - 华j + d ( ) 5 观察3 1 设一个2 一点z 和两个点钛讹相邻且d ( u ) d ( 让) ( 1 ) 如果d ( v ) = 2 ，则d ( u ) 7 一1 5 一 二、关于非负特征图的线性染色问题 ( 2 ) 女u 果d ( u ) = 3 ，贝0d ( u ) 5 令等式( 牢) 中k = 9 定义一个初始权函数叫：如果u y ( g ) ，则伽( ) = 7 d ( v ) 一1 8 ；如果，f ( g ) ，则w ( f ) = 2 d ( f ) 一1 8 权转移规则如下： ( r 3 ) 设u 是一个度至少3 的点，乱是相邻于u 一个2 点 如果d ( u ) 7 ，则u 给乱的权为百6 1 ， 如果d ( u ) = 6 ，则v 给让的权为西4 7 ， 如果d ( u ) = 5 ，则 给乱的权为面3 3 ， 如果c f ( 秒) = 4 ，则u 给 1 2 的权为警； 如果d ( ) = 3 ，则u 给乱的权为i 设w 7 为权转移结束后的新权函数只需验证对于所有的z v ( a ) uf ( a ) 有w 7 ( z ) 0 ，且存在某个x + v ( a ) u f ( g ) 使得2 1 ) 7 ( z + ) 0 设，f ( g ) 因为g ( a ) 9 ，所以d ( f ) 9 则w 7 ( ，) = 叫( ，) = 2 d ( f ) 一1 8 o 设v y ( g ) ，则d ( u ) 2 如果d ( v ) 7 ，则由( r 3 ) ， w 7 ( u ) = 叫( u ) 一暑佗z ( 钉) 7 d ( v ) 一1 8 一嚣d ( u ) = 鼍d ( u ) 一1 8 酱x7 1 8 = ； 血兀果d ( u ) = 6 ，贝0 由( r 3 ) ， w 如) 2 4 一西4 7x6 = ； 如果d ( v ) = 5 ，则由( r 3 ) ， w ”) 1 7 一面3 3 5 = 如果d ( v ) = 4 ，则由( r 3 ) ， w 伽) 苎1 0 一萼4 = 一1 6 二、关于非负特征图的线性染色问题 女口果d ( ) = 3 ，贝0 由( r 3 ) ， w 伽) 3 3 3 = ； 假设d ( v ) = 2 ，则叫( u ) = 7 d ( v ) 一1 8 = 一4 设。，y 为u 的邻点且满足 d ( z ) 冬d ( 可) 如果d ( y ) 7 ，则由( r 3 ) ，转器给u 所以， 删7 ) - 4 + 面6 1 = 击 假设d ( u ) 6 由观察3 1 ，d ( x ) 3 如果d ( z ) 4 ，f 主t ( r 3 ) ，z ，y 分别转百1 9 给 u ，所以 w 7 ( 口) - 4 + 2 警= ； 如果d ( z ) = 3 ，由观察3 1 ，d ( y ) 5 ，所以 叫7v ) 一4 + 嚣+ 3 = 丽2 证毕! 第4 部分m 5 且g ( g ) 1 0 在这种情况下，l c l = k = f 虿m 1 + 1 4 如果m 7 ，则由第三部分可知结 果成立因此假设5 m 6 即l c i = 4 且z x ( g ) 6 断言a 隐含着下面的断言4 1 ： 断言4 1 设x u v y 是一条路且满足d ( u ) = d ( v ) = 2 ，则d ( x ) 5 ，d ( y ) 5 断言4 2 若一个3 一点乱相邻于三个2 点，则每个2 点都相邻一个度至少为4 的点 证明：假设断言不正确设乱相邻三个2 一点z ，y ，z ，设z 7 ，y 7 ，z 7 分别为z ，y ，z 的不 同于乱的邻点由断言4 1 ，z 7 ，y 7 ，z 7 的度数至少为3 假设d ( x 7 ) = 3 设8 1 ，8 2 为z 7 的不同与z 的邻点，如图2 1 所示令 h = g z ，则h 是一个n c - 图且满足( g ) a ( h ) m 和g ( h ) g ( c ) 1 0 由g 的极小性，日有一个线性一染色c 应用颜色集合c = i 【1 ，2 ，3 ，4 我们考虑 一1 7 二、关于非负特征幽的线性染色问题 下而两种情况： 图2 1 ：断言4 2 中的结构 情况1c ( u ) = c ( z ，) 如果c ( s 1 ) = c ( s z ) ，我们用c c ( u ) ，c ( s ) ) 中在y 和z 上最多出现一次的 颜色染x 如果c ( s 1 ) c ( s 。) ，我们用不同于c ( 让) ，c ( 可) ，c ( 名) 的颜色染z 因为 i c i = 4 ，这样的颜色总是存在的 情况2c ( u ) c ( z ，) 如果存在个颜色a c c ( u ) ，c ( z m 至多在s 。和s 2 上出现一次，同时 至多在y 和z 出现一次，则给z 染n 否则，不失一般性，假设c ( z ) = 1 ，c ( u ) = 2 ， c ( s a ) = c ( s 2 ) = 3 ，c ( ! ，) = c ( z ) = 4 首先，给x 染2 然后，如果c ( 可7 ) = c ( z 7 ) = 1 ， 给乱染3 ；否则，给 i t 染1 在上面的每一种情况，我们都可以得到g 的一个线性k 染色这与g 的选 取矛盾因此，d ( z7 ) 4 同理可证，d ( v ) 4 ，d ( 2 7 ) 4 断言4 2 证毕! 断言4 3 不存在两条路7 2 1 7 2 2 u 5 和v l v 2 y 3 使得d ( 札1 ) = d ( u 3 ) = d ( v 2 ) = 3 ， d ( u 2 ) = d ( u 4 ) = 2 ，且? 2 3 和v 2 相邻 证明：假设g 包含这样两条路，如图2 2 所示设h = g 一乱2 则日是一个n c 图 且满足a ( h ) a ( v ) 和g ( h ) 9 ( a ) l o 由g 的极小性，日有一个线性k 染 色c 应用颜色集合c = 1 ，2 ，3 ，4 ) 不失一般性，考虑下面两种情况： 一1r 一 二、关于非负特祉图的线性染色问题 情况1c ( u 4 ) c ( 忱) 设w 1 ，? t ，2 ( “2 ) 为t l i 的邻点如果c ( l t i ) c ( 札3 ) ，我们用c c ( 札1 ) ，c ( t 3 ) ，c ( 叫1 ) ) 中的颜色染u ：如果c ( u 1 ) = c ( z z 。) ，我们用c ( c ( u - ) ，c ( 叫，) ，c ( 耽) ) 中的颜色染 乱2 w l w 2 图2 2 ：断言4 3 中的子结构 情况2c ( u 4 ) = c ( v 2 ) = 1 如果c ( 私，) = c ( u 3 ) ，我们用c 1 ，c ( “- ) ，c ( 毗) ) 中的颜色染t , 2 假设c ( 札z ) c ( u 3 ) ，设c ( u ，) = 2 ，c ( u a ) = 3 如果4 在集合 c ( 伽- ) ，c ( 叫z ) ) 中至多出现一次，我 们给“2 染4 因此，假设c ( w 1 ) = c ( w 2 ) = 4 容易看到存在一个颜色a 2 ，4 ) 在 集合 c ( t ) ，c ( u 3 ) ，c ( 钍5 ) ) 中最多出现一次我们给1 1 , 2 染3 ，然后改染i , 3 为q 断言 4 3 证毕! 令等式( 牢) 中知= 1 0 定义一个初始权函数叫：如果v y ( g ) ，则( u ) = s d ( v ) 一2 0 ；如果f f ( g ) ，则w ( f ) = 2 d ( f ) 一2 0 权转移规则如下： ( r 4 1 ) 每一个度数至少是6 的点转西5 5 给相邻2 点 ( r 4 2 ) 每一个5 点转4 给相邻2 一点 ( r 4 3 ) 一个4 一点转警给相邻2 一点 一1 9 二、关于非负特征图的线性染色问题 ( r 4 4 ) 设3 一点钉和2 一点札相邻如果“相邻两个3 一点，则钞给u2 ；否则，u 给u 4 3 设w 7 为权转移结束后的新权函数只需验证w ，满足( i ) 和( i i ) 设厂f ( g ) 因为9 ( g ) 1 0 ，所以d ( ，) 1 0 如果d ( 厂) = 1 0 ，则叫7 ( ，) ： w ( f ) = 0 如果d ( f ) 1 1 ，则7 ( ，) = w ( f ) = 2 d ( f ) 一2 0 之2 设u y ( g ) 因为d ( g ) 2 ，所以d ( u ) 2 如果d ( v ) 6 ，则由( r 4 1 ) ， 叫( u ) 训( ) 一篱d ( u ) = 8 d ( v ) 一2 0 一嚣d ( ) = i d ( v ) 一2 0 j 如果d ( v ) = 5 ，则由( r 4 2 ) ， w 7 ( 口) 2w ( v ) 一4 5 = s d ( v ) 一2 0 2 0 = 0 如果d ( v ) = 4 ，则由( r 4 3 ) ， w 伽) w ( v ) 一4 警= 1 2 假设d ( v ) = 3 ，则叫( u ) = s d