（应用数学专业论文）图的bbc染色.pdf

渺_ 图白g b b c 染色 l i i i iii iii ii i i i i l l l l l l l li il 18 0 4 3 8 5 摘要 一个有序对g = ( ve ) 称为一个无向图，其中y 是一个有限集合，e 是y 中的不同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图 g 的边通常用y ( g ) ，e ( c ) 分别表示图g 的顶点集合与边集合没有重边和环 的图叫做简单图 图g 的一个正常k 顶点染色是指一个映射毋：v 一 1 ，七) ，使得对任意 t i t ，e ( g ) ，满足咖( t i ) ( u ) 若图g 有一个正常k 点染色，那么就称图g 是 k 点可染色的图g 的色数是指g 有一个正常k 顶点染色的数七的最小值，用 x ( c ) 表示 令是g 的生成子图，( g ，日) 的一个b b c 一七一染色是一个映射，： v ( c ) 一 1 ，2 ，七) ，满足( 1 ) 若u e ( h ) ，则l ，( u ) 一，( u ) i 2 ；( 2 ) 若u u e ( g ) e ( 日) ，则i ，( t t ) 一f c v ) i 1 ( g ，h ) 的b b c - 染色数就是指最小的整数 七，使得( g ，) 有b b c 一七一染色，记作x b ( c ，h ) = 七 近年来，图的染色概念不断演化，出现了很多与频率分配相关的染色如： l ( 2 ，1 ) 一标号染色。距离2 一染色，r a d i o 一染色等概念b b c - 染色概念最早由 日町o b r o e r s m a 教授在第2 9 届国际计算机方面的图理论研讨会议一h 提出的它是 一种与网络频率分配问题相关的图的染色问题到目前为止，已经做出了不少结 果 已经证明了当图g 的生成子图阿分别是一棵生成树、一条h a m i l t o n 路、 一个完美匹配或者一些不相交的独立星图时，( g ，) 的b b c - 染色数上界与图 的正常顶点染色的关系并证明了当g = 丁uc 为h a l i n 图，且g 以生成树丁 为生成予图时，( g ，丁) 的b b c 一染色数 t 摘要 本文主要讨论一些具体图类的b b c 染色问题在第二章中主要讨论对 于图g 的m y c i e l s k i 图m ( g ) ，研究x b ( a ，t o ) 与x b ( m ( g ) ，r ) 之间的关系以 及x b ( g ，t o ) 与灿( f ( g ) ，p ) 之问的关系，其中殆为g 的生成树，r ，p 分别 为m ( g ) 的两类特殊生成树第三章中主要讨论了当图g 为广义p e t e r s e n 图 c ( n ，七) ，且c ( n ，k ) 的生成子图是一棵生成树死时，c ( n ，k ) 关于蜀的b b c 一 染色数，即x b ( c ( n ，七) ，t o ) 的值以及当c ( n ，七) 的生成子图是完美匹配m 时， a ( n ，k ) 关于m 的b b c - 染色数，即x b ( o ( n ，七) ，m ) 的值 关键词：b b c 染色：生成树； 完美匹配；m y c i e l s k i i 型；f 义p e t e r s e n ； h a l i n 图 -、0爹 t h eb a c k b o n ec o l o r in go fg r a p h s a b s t r a c t a g r a p hg = ( ve ) c o n t a i n saf i n i t en o n e m p t ys e tv o fo b j e c t sc a l l e dv e r t i c e s a n das e teo f2 - e l e m e n ts u b s e t so fvc a l l e de d g e s t h es e tva n dea r et h ev e r t e x s e ta n de d g es e to fg ag r a p hw h i c hd o e sn o tc o n t a i np a r a l l e le d g e so rl o o pi sc a l l e d s i m p l eg r a p h a k - c o l o r i n go fag r a p hg i sam a p p i n gff r o mt h ev e r t e xs e tv ( c ) t ot h ec o l o r s e t 【1 ，2 ，七) w es a yt h a tf i sp r o p e ri ff ( v ) f ( u ) f o ra n yt w oa d j a c e n tv e r t i c e s ua n du t h ec h r o m a t i cn u m b e r ，d e n o t e db yx ( c ) o fgi st h es m a l l e s tks u c ht h a tg h a sap r o p e rk - c o l o r i n g g i v e nag r a p hga n di t ss u b g r a p hh ，ab a c k b o n e - k c o l o r i n go f ( g ，h ) i sak c o l o r i n gf ：v ( c ) - - - - - - d , 1 ，2 ，七) s u c ht h a tl f o ) 一，( ) l 2i f u e ( h ) a n dl f ( u ) 一，( u ) i 1i f 牡u e ( g ) e ( h ) t h eb a c k b o n cc h r o m a t i cn u m b e ro f ( g ，h ) i st h es m a l l e s ti n t e g e rks u c ht h a t ( g ，h ) h a sab a c k b o n e k - c o l o r i n g ，d e n o t e d b yx b ( c ，) i nr e c e n ty e a r s ，m a n yk n o w nc o l o r i n gp r o b l e m sr e l a t e dt of r e q u e n c ya s s i g n m e n t f i ti n t ot h i sg e n e r a lf r a m e w o r k w ew i l ld i s c u s st h ef o l l o w i n gt y p e so fp r o b l e m s ，s u c h a sd i s t a n t - 2c o l o r i n g ，r a d i oc o l o r i n ga n ds oo n t h eb a c k b o n ec o l o r i n gw a sf i r s t i n t r o d u c e db yh 叮o b r o e r s m a ，w h oh a dd o n eal o to fw o r ko ni t i th a sp r o v e dt h er e l a t i o n s h i pb e t w e e nt h eu p p e rb o u n d so fx b ( a ，h ) a n dx ( g ) ， w h e r egi sag r a p ha n dhi sr e s p e c t i v e l yas p a n n i n gt r e e ，as p a n n i n gp a t h ，ap e r f e c t m a t c h i n go rs o m ep a i r w i s ed i s j o i n ts t a r s i ta l s oh a sp r o v e dx 6 ( g ，丁) ，w h e r eg = 丁uc i sah a l i ng r a p ha n dti sas p a n n i n gt r e eo fg i nt h i st h e s i s ，w em a i n l ys t u d yx b ( g ，) ，w h e r egi sam y c i e l s k ig r a p h ，ag e n e r a l m a b s t r a c t i z e dp e t e r s e ng r a p ha n dah a l i ng r a p ha n ds oo n ，a n dhi sas p a n n i n gt r e e ，as p a n n i n g p a t ha n dap e r f e c tm a t c h i n g i nc h a p t e r1 ，w el e tgb eag r a p ha n d 死b eas p a n n i n gt r e eo f g l e tm ( g ) b et h e m y c i e i s k ig r a p ho fg r a p hg w en e e dt os t u d yt h er e l a t i o n s h i pb e t w e e nx b ( g ，乃) a n d ( m ( g ) ，r ) w i t hr e s p e c tt og i v e ns p a n n i n gt r e er o fm ( g ) w ea l s on e e dt os t u d y t h er e l a t i o n s h i pb e t w e e nx b ( g ，7 a ) a n d 勋( ，( g ) ，p ) w i t hr e s p e c tt og i v e ns p a n n i n g t r e er o f ，( g ) t h e nw en e e dt oc h a r a c t e r i z ex b ( m ( c ) ，p ) ，i fg i sab i p a r t i t e g r a p h ，ac o m p l e t eg r a p ha n dah a l i ng r a p h i nc h a p t e r2 ，l e tgb eag r a p ha n dhb ea s u b g r a p ho fg i nt h i sp a p e lw en e e dt oc h a r a c t e r i z et h eb a c k b o n ec h r o m a t i cn u m b e r o fg e n e r a l i z e dp e t e r s e ng r a p h ，w h e r et h es u b g r a p hi st h es p a n n i n gt r e et oo rt h ep e r f e c t m a t c h i n g f k e yw o r d s ：b a c k b o n ec o l o r i n g ；s p a n n i n gt r e e ；p e r f e c tm a t c h i n g ；m y c i e l s k ig r a p h ；g e n e r a l i z e dp e t e r s e ng r a p h ；h a l i ng r a p h hti-毒 h y 产ll，l 目录 摘要 i a b s t r a c t i 目录v 1 绪论1 1 1 基本概念l 1 2b b c 染色问题的研究概况 3 1 3 本文的主要结果8 2 m y c i e l s k i 图的b b c 一染色1 1 2 1 一般图的m y c i e l s k i 图的b b c - 染色数1 1 2 2 几类特殊图的m y c i c l s k i 图的b b c 染色数1 4 3 广义p e t e r s e n 图的b b c 染色2 0 3 1 主要引理2 0 3 2 生成子图为树的b b c 染色2 l 3 3 生成子图是完美匹配2 6 参考文献2 9 在学期间的研究成果及发表的论文3 l 致谢3 2 学位论文独创性声明及授权声明3 3 学位论文诚信承诺书3 4 n 鼍|j-1， “y tlll 1 1 基本概念 1绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号 一个有序对g = ( ve ) 称为一个无向图，其中y 是一个有限集合，e 是y 中的不同元素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元素叫做图 的边通常用v c g ) ，e ( g ) 分别表示图g 的顶点集合与边集合没有重边和环的 图叫做简单图除非特别指出，本文研究的图均指有限简单无向图 常用t ，u 表示g 中的点，e 表示g 中的边若边e = t l 口e ( g ) ，则说t i ， 在 g 中相邻；这时又说t 和 是e 的端点，也说 ，t 与e 相关联设u 是一个顶点，u 的全体邻点所形成的集合叫做 的邻域，记作( u ) 与口相关联的边的条数叫做 u 的度数，记作d ( u ) 对于图g ，用a c c ) ，g c c ) ，i c l ，t c 分别表示g 的最大度，围 长，阶以及g 的一个生成树 如果能将图g 画在平面上，使得它的边仅在端点处相交，则称图g 是可平面 图图的这种平面上的画法称为图的平面嵌入或称为平面图 图g 的一个正常k 顶点染色是指一个映射毋：v _ 1 ，七) ，使得对任意 t l u e ( g ) ，满足妒( u ) 咖( u ) 若图g 有一个正常k 点染色，那么就称图g 是 k 点可染色的图g 的色数是指g 有一个正常k 顶点染色的数k 的最小值，用 x c g ) 表示 图g 的一个顶点色列表l 是一个颜色集合簇，它指定g 的每个顶点口一个 颜色集合l ( ) 若g 有一个正常的顶点染色，使得对每一个顶点u v c e ) ，有 咖( ) l ( u ) ，则称g 为l 顶点可染的，或者称咖是g 的一个l 一染色也称g 是 l 一列表染色 1 l 绪论 _ 一一。一一一一一 i 对于g 的任何一个满足i 三( t ，) i k ( v v y ( g ) ) 的列表厶g 都是一顶点 可染的，则称g 是南点可选择的，简称g 是七可选择的g 的顶点列表色数是使 得g 是七可选择的最小的非负整数k 显然，若g 是k 可选择的，则g 一定是k 可染色的 令日是g 的生成子图，( g ，) 的一个b b c k 一染色是一个映射，： v ( a ) 一 1 ，2 ，七) ，满足( 1 ) 若 u v e ( ) ，则l f ( u ) 一厂( ) i 2 ；( 2 ) 若u e ( g ) e ( 玎) ，则j f ( u ) 一，( 1 ，) i 1 ( c ，h ) 的b b c 一染色数就是最小的整数k ， 使得( g ，h ) 有b b c 一七一染色，记作舶( g ，日) = 南 图g 关于一个生成子图日的b b c 一染色数随日的变化而变化，而且同为 c 的生成树互和正，x b ( c ，n ) 和( g ，t 2 ) 未必相同，如下图： y 弋、 7 、， ，7 。f r， ( 冷毯 、j j 萝 g 3 、 ，一 除 一 巡 6 生成树巧 图1 1 ，4 5 4 7 j j 、 、又、 一 x 2 ，l 3 生成树瓦 由上图，由于g 为完全图，为了满足正常染色，则g 中每个顶点需染不同颜 2 2 5 l 绪论 色，且由b b c 一染色定义，易i 正x b ( a ，正) = 7 。( g ，死) = 6 由简单图g 产生的m y c i e l s k i 图m ( g ) 是一个简单图：其中顶点集合为 y ( m ( g ) ) = vu u u 叫) ，这里v = v ( a ) = v l ， 0 2 ， ，u = 乱l ，u 2 ，u n ) ； 边集合为e ( m ( g ) ) = e ( a ) u 0 i u j l v i y ( g ) ，u s u 且v i 0 j e ( g ) ) u l w u d i = 1 ，2 ，n ) 设3 一正则图g 的顶点集和边集分别为v ( a ) = u o ，u l ，u n - i ； 0 0 ，u l ，一i ) ， e ( a ) = ( t l t + 1 ) ，( u i 0 i ) ，( v i 0 i + 七) l i = 0 ，1 ，n - l ，其中的下标取模礼，且n 5 ， l k n ，竹2 k ，则称图g 为广义p e t e r s e n 图，记为g m ，七) 本文所用术语和符号基本上与文献【1 1 、【2 】中一致本节中未介绍的其他图 论术语将在必要时予以阐述 1 2b b c 染色问题的研究概况 图染色问题的研究来源于著名的四色问题，即在平面上任何一张地图，总可 以用至多四种颜色给每一个国家染色，使得任何两个相邻国家( 公共边界上至少 有一段连续曲线) 的颜色是不同的关于平面图的染色问题是图论研究的热点也 是难点 近年来，图的染色概念不断演化，文献【3 】中提到了l ( 2 ，1 ) 一标号染色，距离 2 一染色，r a d i o 一染色等概念b b c 一染色概念最早由町o b r o e r s m a 教授在 第2 9 届国际计算机方面的图理论研讨会议上提出的他是一种与网络频率分配问 题相关的图的染色问题该染色中，图是用来描述网络信息传输系统的一种模型。 其中顶点表示网络传输站点( 包括发射点，接收点，中转点) ，若两个网络传输站点 之间的距离比较近，当其发射相同或相似频率信息时会产生相互干扰，则在图中 表示该两个顶点相邻那么在设计网络线路时，对该段线路的设计提出了更高更 多的限制要求这个问题相当于对图中的某些边给出特定的限制，使得网络频率 信息保持在可接受的水平，不至引起相互干扰到目前为止，该染色方向已经做出 3 1 绪论 了不少结果文献 4 】中主要研究当图g 的生成子图是一棵生成树或者是一条 h a m i l t o n 路时，( g ，h ) 的b b c 一染色数上界与图的正常顶点染色的关系文献 【5 】主要研究当图g 的生成子图h 是一个完美匹配时，( g ，h ) 的b b c 一染色数 与图的正常顶点染色的关系文献【6 】、【7 】中主要研究当图g 的生成子图日分 别是完美匹配或几个顶点不相交的星图时，( g ，日) 的a b b c 一染色数与图的 正常顶点染色的关系文献【8 1 研究以t 为生成树的h a l i n 图g = t uc ，( g ，t ) 的b b c - 染色数 目前对图的b b g 一染色的研究进展来看，主要有以下结果： 首先定义如下符号： 7 ( 七) = m a x b b c ( g ，t ) ：t 是g 的生成树，x ( a ) = 七 p ( k ) = m a x b b c ( g ，p ) ：p 是g 的h a m i l t o n i a n 路，x ( a ) = 七) m ( k ) = m a x b b c ( g ，m ) ：m 是g 的完美匹配，x ( a ) = 七) a ( 七) = m a x b b c x ( g ，t ) ：t 是g 的生成树，x ( c ) = 七) r ( 七) = m a x b b c x ( g ，p ) ：p 是g 的h a m i l t o n i a n 路，x ( c ) = 七) 地( 七) = m a x b b c x ( g ，m ) ：m 是g 的完美匹配，x ( a ) = 七 & ( 七) = m a x b b c x ( a ，s ) ：s 是g 的顶点不相交的星图构成的生成子图， x ( a ) = 七) 定理1 1f 4 】图g 为连通图，g x ( c ) = k ，贝u r ( k ) = 2 k 一1 定理1 2 【4 】图g 含有h a m i l t o n 路，且x ( c ) = 七，k l ，则p ( k ) 取值如下： ( a ) 当1 k 4 时，则p ( k ) = 2 k 一1 ( b ) 当k = 5 或6 时，则p ( 5 ) = 8 ；p ( 6 ) = 1 0 ( c ) 当七7 且七= 4 t 时，则p ( 4 t ) = 6 t ( d ) 当k 7 且七= 4 t + l 时，则p ( 4 t + 1 ) = 6 t + 1 ( e ) 当七7 且七= 4 t + 2 时，则p ( 4 t + 2 ) = 6 t + 3 4 氓 ； ， 绪论 ( f ) 当k 7 且k = 4 t + 3 时，则p ( 4 t + 3 ) = 6 t + 5 定理1 3 【5 l 图g 含有完美匹配，且x ( v ) = k ，k 1 ，则m ( k ) 取值如下： ( a ) 当k = 4 时，则m ( 4 ) = 6 ( b ) 当k = 3 t 时，则m ( 3 t ) = 4 t ( c ) 当k = 3 t + 1 且k 4 时，则m ( 3 t + 1 ) = 4 t + 1 ( d ) 当k = 3 t + 2 时，则m ( 3 t - f2 ) = 4 t + 3 定理1 1 ，1 2 ，以及定理1 3 是当图g 为一般图时，生成子图h 分别取树、 路、完美匹配时，图g 关于生成子图日的b b c 一染色数的上界以下定理1 4 主要研究了a b b c 一染色 令h 是g 的生成子图，( g ，) 的一个a b b c k 一染色( 入2 ) ，是一个映 射f ：v ( e ) 一 1 ，2 ，七) ，满足( 1 ) 若t l u e ( ) ，则l f ( u ) 一，( u ) i 入；( 2 ) 若 仳u e ( g ) f ( ) ，则i f ( u ) 一，( u ) l 1 ( g ，日) 的a b b c - 染色数就是最小 的整数k ，使得( g ，日) 有a b b c 一七一染色，记作b b c x ( g ，h ) = k 定理1 4 【6 】如果图g 含有完美匹配，且x ( g ) = k ，k 1 ，a 2 ，则帆( 七) 取值如 下： ( a ) 当2 k a 时，则帆( 七) = k + 入一1 ( b ) 当入+ l k 2 a 时，则慨( 七) = 2 k 一2 ( c ) 当k = 2 a - f1 时，则 以( 七) = 2 k 一3 ( d ) 当k = ( 入+ 1 ) ，其中t 2 时，则慨( 七) = 2 t a ( c ) 当凫= t ( a + 1 ) + c ，其中t 2 ，1 c 学时，则a 以( 七) = 2 t a - f 2 c 一1 ( f ) 当k = ( a + 1 ) + c ，其中t 2 ，学c 入时，则 以( 七) = 2 t a + 2 c 一2 通过上述已经证得的结论，我们自然要问这样一个问题，既然可以得出 慨( 忌) ，那么a ( 七) ，r ( 七) ，& ( 七) 的值r i g ? 关于a ( 七) ，r ( 七) 还没有研究成果，对于 5 1 绪论 文( 七) 在具体的图当中已经给出结果例如在分割图中，有如下结果： 若图g = ( ve ) 的项点集y 可以被剖分为和k ，使g 【】为团，g 【k 】为 独立集。则称g 是一个分割图 定理1 5 【7 j 如果图g 是一个分割图，且x ( a ) = k 2 ，则& ( 七) 的取值如下： ( a ) 当k = 3 ，a 2 或k 4 ，a = 2 时，则& ( 七) k + a ( b ) 当非( a ) 时，则又( 七) k + a 一1 对于定理1 5 的结果推进有如下结果： 定理1 6 【6 】如果图g 满足x ( g ) = k ，k 1 ，则& ( 七) 取值如一f ： ( a ) 当k = 2 时，则艮( 2 ) = 2 a 1 ( b ) 当3 k 2 a 一3 时，则是( 七) = 警 + a 一2 ( d ) 当2 a 一1 k 2 a ，且入= 2 时，则文( 七) = k + 2 a 一2 ( e ) 当2 a 一2 k 2 a 一1 ，且入3 时，则民( 七) = k + 2 a 一2 ( f ) 当k = 2 a ，入3 时，则& ( 七) = 2 k 一1 ( g ) 当k 2 a + 1 时，则叉( 七) = 2 k 一【女j 定理1 7 【7 】如果图g 是一个分割图，x ( a ) = k 2 ，则慨( 七) 的取值如下： ( a ) 当k = 2 时，则a 以( 七) sa + 1 ( b ) 当k 4 且k m i n ，学) 时，则地( 七) = k + 1 ( c ) 当k = 9 或k 1 1 且丁k + 6sas ； 时，则地( 七) = k + 2 ( d ) 当k = 3 ，5 ，7 且a f 时，则慨( 七) = + a ( e ) 当k = 4 ，6 或k 8 且k 1 + 1 时，n m a ( k ) = 1 + a + 1 在上述研究的基础上，给出了很多对于一个具体的图类，其b b c 一染色的一 些结果，首先对于分割图，有如下结果： 6 4 、 ； l 绪论 定理1 8m 如果图g 是一个分割图，则有 ( a ) 对于连通图g 的每棵生成树丁，有骼( g ，t ) x ( c ) - i - 2 ( b ) 若u ( g ) 3 ，g 包含一条h a m i l t o n i a n 路，则对g 的每条h a m i l t o n i a n 路p ，有x b ( c ，p ) x ( c ) + 1 这里的u ( g ) 为图g 的团数 其次研究了当图g 为一个h a l i n 图以及圈时。有如下结果： 定理1 9 【8 l 如果图g 为h a l i n 图，g = 丁uc ，g 的生成树丁的顶点集可划分为 xuy 两个独立集。则有： ( a ) 4 x b ( c ，t ) 5 ； ( b ) x b ( g ，t ) = 5 当且仅当l s ( 丁) i 是奇数，且s ( t ) x 或s ( t ) y 其中i s ( t ) i 是生成树t 中l - 度点的个数 定理1 1 0 【9 】图g 是一个圈，其中m 是g 的一个完美匹配，则有x b ( c n ，m ) 3 以最大度，围长和平均度作为限制条件的b b g 一染色数，有以下一些结 果： 定理1 1l f lo l 令a n ，则存在一个最大度为的图g ，和g 的生成子树l 使 得x b ( c ，t ) = + 2 定理1 1 2 【lo 】若g 是一个最大度为的图，其中日是g 的d 一退化子图，则有 x b ( c ，h ) a + d + 1 定理1 13 【1 0 1 若g 是一个最大度为的图，其中m 是g 的完美匹配，则有 x b ( c ，m ) + 1 定理1 1 4 1 1 1 若g 是满足m a d ( g ) 3 的图，则g 中存在一棵生成树t ，使得 x b ( g ，t ) 4 7 1 绪论 定理1 1 5 【1 1 j 令g 是围长g ( v ) 4 的连通平面图，则g 中存在一棵生成树丁，使 得x b ( c ，t ) 4 以上是目前在b b c 染色方面已经做出的一些结果，下面也有一些问题值得我 们进一步进行研究与探讨： 问题1 ：当入3 时，a ( 七) ，r ( 七) 的值是怎样的? 问题2 ：当g 为不含三角形的图，是否存在常数c ，使得x b ( g ，t ) x ( g ) + c 问题2 已经被学者j o z e f m i s k u f , r i s t es k r e k o v s k i 和m a r t i nt a n c e 征明这样的 c 是不存在的 问题3 ：对于平面图g ，其中丁为g 中的任意一一棵生成树，利用四色定理，可 证x b ( g ，t ) 7 ，可否将7 这个上界降为6 7 问题4 ：对于平面图g ，其中丁和p 分别为g 中的任意一棵牛成树和任意一 条h a m i l t o n 路，不利用四色定理，如何证明x b ( g ，丁) ，x b ( g ，尸) 的上界 问题5 ：对于平面图g ，其中m 为g 中任意一个完美匹配，是否有 x b ( g ，m ) 5 问题6 ：当g 是弦图时，其中t 是g 生成子图，尸是g 生成路，则有 x b ( g ，p ) x ( c ) + 4 ，那么( g ，t ) 的值如何 1 3 本文的主要结果 对于b b c 染色问题，自然产生这样几个问题：首先对于一般的图，当其生成 子图分别为生成树、路以及完美匹配时，他的b b c 一染色数的上界分别是多少? 其次研究某些具体的图类时，当其生成子图分别是生成树、路或完美匹配时，其 对应的关于其生成子图的b b c 一染色数是多少? 本文在前人的工作基础上，围绕具体图类的b b c 一染色问题展开研究 r a ； l 绪论 在第二章中，基于图g 的m y c i e l s k i 图m ( g ) ，研究x b ( c ，t a ) 与x b ( m ( g ) ，r ) 之间的关系以及x b ( g ，t c ) 与x b ( m ( g ) ，t ”) 之间的关系，其中t a 为g 的生成 树，r ，r 分别为m ( g ) 的两类特殊生成树并给出当g 为二部图，完全图以及 h a l i n 图时，x b ( m ( g ) ，p ) 的值主要结果如下： ( 1 ) g 为非平凡连通图，则x b ( g ，t c ) x b ( m ( g ) ，r ) x b ( a ，t a ) + 1 ( 2 ) g 为非平凡连通图，则x b ( g ，亿) 冬x b ( m ( c ) ，7 w ) sx 6 ( g ，) + 1 ( 3 ) g 为连通的二部图，则x b ( m ( g ) ，p ) = 4 矧懒夸巴茎瓮啬 ( 5 ) g 为h a l i n 图，g = 丁uc 此处t a = t ，则有 c m c g ，r ，= 兰：銎善? 奇轮时 在第三章中，主要研究了当图g ( n ，七) 为广义p e t e r s e n 图时，且其生成子图 分别取生成树和完美匹配时，图g ( n ，七) 关于生成子图的b b c - 染色数主要有 ( 6 ) 对于n 三o ( m o d 2 ) ，七三l ( m o d 2 ) 的广义p e t e r s e n 图g ( n ，七) ，其中t o 为 g ( n ，k ) 的生成树，则有x b ( a ( n ，七) ，t o ) = 3 ( 7 ) 对于礼三o ( m o d 2 ) ，七三o ( m o d 2 ) ，且n 2 k 的广义p e t e r s e n 图g ( 他，七) ， t o 为g ( n ，七) 的生成树，则有 c g ，七，= ：雪薹凳霎釜： 9 1 绪论 其中d 为7 7 和k 的最大公约数，记作d = ( 礼，七) ( 8 ) 对于礼三l ( m o d 2 ) ，1 k n 的广义p e t e r s e n 图g ( n ，七) ，t o 为g ( 礼，k ) 的生成树，有( g ( 礼，七) ，t o ) = 4 ( 9 ) 对于广义p e t e r s e n 图g ( n ，七) ，其中m 是g ( n ，k ) 的完美匹配，则 x a c g c 咒，七， 彳，= 三： 霎善_ 。( m 。d 2 ) ，七三1 ( ”2 。d 2 ) 1 0 文 i l 譬 ， 2 m y c i e l s k i 图的b b c - 染色 研究图的b b c 一染色是图的染色理论中的一个重要研究课题本节讨论对 于图g 的m y c i e l s k i 图m ( g ) ，研究x b ( g ，t c ) 与x b ( m ( c ) ，r ) 之间的关系以及 x b ( g ，t a ) 与x b ( m ( g ) ，p ) 之间的关系，其中乃为g 的生成树，r ，p 分别为 m ( g ) 的两类特殊生成树 对于g 的一棵生成树，我们来给出m ( c ) 中一棵生成树7 v ：记【v u 】= v i u j l v i ，y ( g ) ，u ，且仇吻e ( g ) ) ，记g o = m ( g ) 【，u 叫】，f 【v u l 取t i = t g u g o u f ，则显然可知属于r 且属于【k 刎的边有且仅有一条，即 i f i = 1 若不然，则r 中含圈本文讨论的图g 都是非平凡连通图 2 1 一般图的m y c i e l s k i 图的b b c 一染色数 定理2 1 对于图g = ( v e ) ，两个从顶点集到颜色集的映射，：v ( a ) 一 【1 ，2 ，七) ，满足对于讹y ( g ) ，( 口) + ，( ) = k + 1 则对于g 中的任何生成 树丁，是( g ，丁) 的一个b b c - k - 染色当且仅当，7 是( g ，t ) 的一个b b c - 七一 染色称，7 互为对称映射 定理2 2g 为非平凡连通图，则x b ( c ，t c ) x b ( m ( g ) ，r ) x b ( a ，t g ) + 1 证明：假设x b ( c ，t c ) = k 左边不等号显然成立，即k x b ( m ( g ) ，r ) 下证 x b ( m ( c ) ，r ) k + 1 由于g 为非平凡的连通图，则k 3 因为x b ( a ，t c ) = k ，所以存在( g ，) 的b b c 一七一染色f c ：v ( a ) 一 1 ，2 ，七) r 中存在 u 】中一条边，不妨设该边为v i o u j o ( 1 ) 若f c ( r i o ) k ，作( m ( g ) ，t i ) 的b b c 一( k + 1 ) - 染色，：y ( m ( g ) ) 一 1 ，2 ，k + 1 ) ，满足：( i ) 铷y ( g ) ，( u ) = 尼( u ) ；( i i ) v ueu ，- 厂( u ) = 七+ 1 ； ( i i i ) f ( w ) = 1 则i f ( v i o ) 一，( o ) i 2 和v u u ，i f ( u ) 一厂( 叫) i = i ( 七+ 1 ) 一l i = 七2 11 2 m y c i e l s k i 图的b b c 一染色 因此，是( m ( g ) ，r ) 的一个b b c 一( k + 1 ) - 染色 ( 2 ) 若，g ( t ，i o ) = k ，作，g 的对称映射f b ：v ( a ) 一 l ，2 ，七) ，其中 v v y ( g ) ，尼( ) = ( k + 1 ) 一尼( ) 下面作( m ( g ) ，丁) 的b b c 一( k + 1 ) 一染 色，7 ：y ( m ( g ) ) 一 1 72 ，k + 1 ) ，满足：( i ) v v y ( g ) ，7 ( ) = 尼( ) ；( i i ) v u u ，7 ( u ) = k + 1 ；( i i i ) ，( 叫) = 1 则，7 ( 仇o ) = 尼( 忱o ) = ( k + 1 ) 一尼( 协o ) = 1 ， 且i 厂7 ( 仇o ) 一，7 ( o ) l = l l 一( 七+ 1 ) i 2 和v u u ，i ，( 锃) 一，7 ( 坩) i = i ( 七+ 1 ) 一1 i = k 2 因此，是( m ( g ) ，r ) 的一。个b b c 一( k + 1 ) - 染色 综上可知，x b ( m ( g ) ，r ) k + 1 证毕 对于g 的生成树死，构造m ( g ) 的另一棵生成树p ：对边仇吻e ( g ) ，称 【vu 】中的边v i u j 和v j u i 为边让吻在m ( g ) 巾的导出边用m l ( t g ) 表示中 1 一度顶点的集合则t 2 = t c m 1 ( ) 仍是一棵树现在按以下规则取f ( g ) ： v v i m ( 乃) ，存在v i o v i e ( t c ) ，则让v i 0 u i f ( g ) 记t 2 = t c m ( ) ，同 样对尬( 死) 中的每个点v 3 ，存在吻o e ( 正) ，则让v j o u j f ( g ) 继续这一过 程，直到瓦只含一个顶点1 1 0 或两个相邻的顶点v o v o ( 1 ) 若瓦只含一个顶点v o ，此时f ( c ) 中已经取了n 一1 条边，则显然u 中 还剩下一个顶点未被f ( a ) 中的边覆盖，不妨设为札。，则取y ( a ) 中一点v l ，使得 功u 。e ( m ( g ) ) ，则由此构造的7 w = t auf ( a ) u 功仳。) u 叫 为m ( g ) 的一 棵生成树 ( 2 ) 若瓦含两个相邻的顶点咖嵋，则取t k + 1 = t k v o ，t k 中有v o v ；e ( 瓦) ， 则将边v o u o f ( g ) ，此时v ( a ) 中已经取了n 一1 条边此时死+ 1 只含一个顶 点t 的构造同( 1 ) 由g 的生成树殆所构造的m ( a ) 的生成树7 w ，我 f - - i 以得出以下结果： 定理2 3g 为非平凡连通图，则有x b ( c ：t g ) x b ( m ( c ) ，7 w ) x b ( c ，t a ) 十1 证明：假设x b ( a ，t c ) = k 左边不等号显然成立，即七x b ( m ( a ) ，7 w ) 下证 1 2 ， ， 一：b 2m y c i e l s k i 图的b b c - 染色 x b ( m ( c ) ，p ) k + 1 由于g 为非平凡连通图，则k 3 因为x b ( g ，t c ) = k ，所以存在( g ，丁( g ) ) 的b b c - k - 染色尼：v ( a ) 一 1 ，2 ，七) 下面作( m ( g ) ，p ) 的b b c - ( k + 1 ) 一染色f ：y ( m ( g ) ) 一 1 ，2 ，k + 1 1 ，满足：( i ) y ( g ) ，f ( v ) = ，g ( u ) ； ( i i ) 1 1 ，2 ，- 1 ，f ( u i ) = f ( v i ) = 尼( 仇) 由于p 中的属于f ( a ) 的边由t a 中边导出，因而v v i u j f ( a ) 一 饥u 。) ， 则仇吻e ( t c ) ，i f ( v i ) 一f ( u j ) i = i f ( v i ) 一f ( v j ) i 2 成立下面只需在保证正常 染色的前提下考虑边功u ，u 。w e ( 7 w ) 的色差至少为2 令，( 饥) = i o 情形1 ：f ( v t ) = k ： ( 1 ) f ( u 。) k 一1 ，由于v t u 。e ( g ) ，故，( 研) f ( u 。) ，故，( u 。) k ，令 f ( w ) = k + 1 则，为m ( a ) 的正常染色，且i ，( 功) 一f ( u 。) i = i k f ( u 。) i 2 ， i f ( u 。) 一，( 叫) i = i f ( u ，) 一( k +