已阅读5页,还剩24页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
摘要 2 0 0 6 午,刘信生等p 2 l 提出了星边染色的概念,若图g 的一个正常边染色满足g 中没 有长为4 的路是2 _ 边染色的,则称此染色是g 的一个星边染色,使得g 有星边染色的最小 颜色数称为星边色数,记作z ( g ) 。奉文的主要工作是对图的星边染色做了初步研究, 文章分五节。 第一节介绍了星边染色的概念及基本性质,给出了路,圈,扇,轮的星边色数,使 用了一种方程的方法确定了几个低阶完全图的星边色数,并给出了一般完全图星边色数 的一个界,最后研究了正常边染色与星边染色之间的关系。 第二节研究了树的星边染色,证明了对最大度为的树t ,存在实数s ( 1 g 2 ) 使 得兄( t ) = e a ,最后利用树的结果给出了h a l i n 图和单圈图星边色数的上界。 第三节研究了超立方体的星边染色,证明了对n ( 3 ) 维超立方体q k ,有n + 1s 砭( q 。) s2 n 一2 。 第四节研究了极大外平面图和极大平面图的星边染色,并界定了它们的星边色数。 第五节利用概率方法给出了一般图星边色数的上界。 关键词:图;正常边染色;星边染色;概率方法 a b s t r a c t i n 2 0 0 6 ,l i u x i n - s h e n g e t a l 嘲i n t r o d u c e d t h e c o n c e p t o f s t a r - e d g e c o l o r i n g o f g r a p h s , 8 s t a r - e d g e0 0 l o r i n go fg r a p hg i sa p r o p e re d g ec o l o r i n go fg s u c ht h a ta n yp a t ho fl e n g t h 4i ngi sn o tb i c o l o r e d t h es t a rc h r o m a t i ci n d e xo fg ,d e n o t e db yz ( g ) ,i st h es m a l l e s t i n t e g e rkf o rw h i c hg a d m i t sas t a r - e d g ec o l o r i n gw i t hkc o l o r s i nt h i sp a p e r ,w em a i n l y d e a lw i t ht h es t a r - e d g ec o l o r i n go fg r a p h s ,0 1 1 1 p a p e rh a v ef i v es e c t i o n s i ns e c t i o no n e , w ew i l li n t r o d u c et h ec o n c e p to fs t a r - e d g ec o l o r i n ga n ds t u d yi t s p r o p e r t i e s ,w eg i v et h es t a rc h r o m a t i ci n d e xo fp a t h s ,c y c l e s ,f a n sa n dw h e e l s w ea l s og e t t h es t a rc h r o m a t i ci n d e xo fs e v e r a ll o wo r d e rc o m p l e t eg r a p h sb yu s i n gae q u a t i o nm e t h o d a n db o u n dt h es t a rc h r o m a t i ci n d e xo fo t h e rc o m p l e t eg r a p h s ,s tt h ee n do fs e c t i o no n e w es t u d yt h er e l a t i o nb e t w e e np m p e re d g ec o l o r i n ga n ds t a r - e d g ec o l o r i n g i ns e c t i o nt w o ,w ew i l lp r o v et h a t 兄( t ) = e a ( t ) ,w h e r et i sat r e ea n d ( 【1 ,2 】) i sar e a ln u m b e r ,b yu s i n gt h er e s u l to ft r e e ,w eb o u n dt h es t a rc h r o m a t i ci n d e xo fh a i i n g r a p h sa n dm o n o c y c l eg r a p h s i n , s e c t i o nt h r e e ,w ew i l ls h o wt h a tn + l z ( q n ) 墨2 n 一2 ,w h e r en 3a n dq ni s r t c u b e i ns e c t i o nf o u r ,w ew i l ls t u d yt h es t a r e d g ec o l o r i n go fm a x i m a lo u t e rp l a n eg r a p h a n dm a x i m a lp l a n eg r a p h a n db o u n dt h e i rs t a rc h r o m a t i ci n d e x i ns e c t i o nf i v e ,b yu s i n gp r o b a b i l i s t i cm e t h o d ,w eg i v ea nu p p e rb o u n do ns t a rc h r o - m a t i ci n d e xo fg r a p h s k e y w o r d s :g r a p h s ;p r o p e re d g ec o l o r i n g ;s t a r - e d g ec o l o r i n g ;p r o b a b i l i s t i cm e t h o d 独创性声明 本人声明所里交的论文足我个人在导师指导下进行的研究工作及取得的研究 成果尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包括其他人已 经发表或撰写过的研究成果,也不包含为状得西北师范大学或其他教育机构的学 位或证书而使用过的材料与我一同工作的同占对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意 签名:主圣纽 日期:z ! 1 1i 盟! 笪 关于论文使用授权的说明 本人完全了解西北师范大学有关保留、使用学位论文的规定,即:学校有权保 留送交论文的复印件,允许论文被查阅和借阅;学校可以公布论文的全部或部分内 容,可以采用影印、缩印或其他复制手段保存论文( 保密的论文在解密后应遵守此 规定) 日期:2 1 1 渤! 丝 i l j l 一 刖吾 边染色是图论研究的重要分支之一,这些年来山于实际问题和理论问题的需 要,数学研究工作者提出了许多关于染色的新概念1 9 7 3 f ,g r i i n b a u m 为了研究 平面图的无圈染色提出了星染色的概念,图g 的星染色是g 的一个正常顶点染色使 得g 中无长为3 的路是2 _ 染色的,使得g 有星染色的最小颜色数称为g 的星色数,记 作舶( g ) 2 0 0 4 年,f e r t i n 等学者在文献【1 6 1 中证明t x ( g ) 5f 2 0 m 。2 0 0 6 年,刘信生 等【3 2 j 提出了星边染色的概念,若图g 的一个正常边染色使得g 中没有长为4 的路是2 - 边 染色的,则称此染色是g 的一个星边染色,使得g 有星边染色的最小颜色数称为星边色 数,记作z ( g ) 然后利用概率方法证明了,当a 7 时,z ( g ) 曼f 1 6 ( a 一1 ) i 1 ,进而 得到,当g 是最大度21 2 的线图时,舶( g ) 1 6 ( a 1 ) 1 1 ,从而部分的改进了【1 6 j 的结 果。 奉文的主要工作是对图的星边染色做了初步研究星边染色与无圈边染色和强 边染色有重要联系。无圈边染色g r i i n b a u m 在文献【2 】中首次引入,随后无圈边染色 得到广泛研究。设g 是图,若图g 的一个正常边染色使得g 中没有2 - 边染色的圈,则 称此染色是g 的一个无圈边染色,使得g 有兀圈边染色的最小颜色数称为无圈边色 数,记作n ,( g ) 。a l o n 等在文献【4 】中得到n 7 ( g ) s6 4 a ,随后m o l l o y 和r e e d 将此结果改进 为n ,( g ) 曼1 6 a 1 l 。2 0 0 5 年,r a h u lm u t h u 等在文献【3 】中证明了,如果围长g ( g ) 9 , 则n ,( g ) 曼6 a ,如果围长g ( g ) 2 2 0 ,贝l j a ( g ) 4 5 2 a 。更多关于无圈边染色的研究 请参见文献聘卜1 0 1 。强边染色山e r d 6 s 和n 蘸t r i l 首次引入,若图g 的一个正常边染色使 得g 中没有长为3 的路是2 - 边染色的,则称此染色是g 的一个强边染色,使得g 有强边染 色的最小颜色数称为强边色数,图g 的强边色数记作s ( g ) 。1 9 8 晦,e r d 6 瘌n e 乱r i i 提 出问题,是否有e 0 ,使得s x ( g ) s ( 2 一) 2 ,他们猜想s f ( a ) g 2 【1 4 1 并且构造出 特殊图g 使得s f ( a ) = ;2 1 9 9 7 年,m o l l o y 和r e e d i 正明了,当e = 0 0 0 2 时,如果充 分大,有s f ( a ) 1 9 9 8 a 2 【l l l 。其它关于强边染色的研究请参见文献【1 2 ,1 3 】由三种 染色定义知,口,( g ) s 兄( g ) ss f ( g ) ,说明星边染色处于兀圈边染色和强边染色的中 佃j 状态,星边色数确定的同时也给出了无圈边色数的一个上界和强边色数的一个下界, 因此研究星边染色对研究无圈边染色和强边染色也有积极的意义。 本文第一节介绍了星边染色的概念及性质,给出了路,圈,扇,轮的星边色数,使 用了一种方程的方法确定了几个低阶完全图的星边色数,并给出了一般完全图星边色数 的一个界,最后研究了正常边染色与星边染色之间的关系。第二至四节分别研究了树, 超立方体,极大外平面图和极大平面图的星边染色,并界定了它们的星边色数。第五节 1 前言 利用概率方法给出了一般图星边色数的一个上界 文中图均指简单无向图,涉及的符号和术语遵从文献【1 7 _ 2 2 】 2 1 星边染色概念及性质 定义1 1 若图g 的一个正常边染色使得g 中没有长为4 的路是2 - 边染色的,则称此染 色是g 的一个星边染色,使得g 有星边染色的最小颜色数称为星边色数,记作兄( g ) 。 根据星边染色的定义可以得到下面性质; 性质1 1 设h 是g 的子图,则z ( h ) s z ( g ) 。 性质1 2 设g 是图,a ( g ) = 表示g 的最大度,则sx :( g ) 1 + f 曰( g ) i i m i ,其中m 是g 的一个最大匹配。 证明下界自然成立。 对于上界,我们给g 的最大匹配m 中所有边均染同一种颜色,其余s j i e ( g ) i i m l 条 边染互不相同的颜色,在此染色下。g 中每条长为4 的路都至少包含2 条相距为l 的边染 不同颜色,显然不会是2 - 边染色的,所以a 兄( g ) s1 + l 曰( g ) i i m i ,定理得证。 性质1 3 设g l ,g 2 ,g 是从g 中去掉a 条边形成的连通分支,则砭( g ) m a x ( z o ( g ) + o rf = 1 ,2 ,k 。 证明设r = m a x x c g 。) 0 = l ,2 ,) ,首先g 的个连通分支都是r 星边染色 的,对去掉的o l 条边染新的口种颜色,此时g 中任意一条长为4 的路尸有两种情况,如 果p 中边都在某个戗中,则p 当然不是2 一边染色的。如果p 中包含去掉的边,则山染色方 法知o l 条去掉的边都使用了唯一的颜色,在p 中不会重复出现,此种情况p 也不是二边染 色的,所以g 有r + 星边染色,定理得证。 直觉上,性质1 2 和性质1 3 的结果是祝糙的,然而它们却都是可达的界,下面我们 讨论几个特铡 对于性质1 2 ,易知砭( g ) = 3 ,z ( k 1 。) = n ,分别满足性质1 2 的上界和下界,值 得注意的是,g 和硒。中奉身没有长为4 的路,从而导致它们的星边色数等于边色数。 现在介绍几个包含岛的特殊图,设树t 是由星s 4 l m 3 ) 的某个悬挂点延伸出一条无 限长的路构成的,则z ( t ) = ( t ) ,符合性质1 2 的下界,而x o ( 心) = 5 ,兄( 蚝) = 9 , 这两个结果符合性质1 2 的上界。 对于性质1 3 ,我们构造了去边后连通和不连通的两个特例。先讨论去边连通 的特例,设g 的顶点按顺时针依次为”1 t j 2 ,地,饥,用h 表示将 1 和v 4 连边e 所构 成的图,容易验证z ( h ( e ) = z ( c 6 ) = 3 ,而也( 日) = m a x 兄( 岛) ) + 1 = 4 符合 性质1 3 的上界。现在讨论去边不连通的特例,构造特殊图风+ l ,风。+ l 是山星& + 1 与 其拷贝s o i 恰有一个非中心公共顶点构成的,设s 冲1 和5 麓l 的中心分别是口和,公 3 1 星边染色概念及性质 共顶点是u ,在日+ l 中去掉边删或删7 都会形成两个连通分支分别同构于& + 1 和& , 而m a x z ( s o - ) ,兄( 晶) ) = n ,x :( 凰件1 ) = n + 1 ,符合性质1 3 的上界。 文献1 1 5 ,1 6 1 中介绍了星染色,星染色是平行于星边染色概念关于顶点的染色,星 色数记作( g ) 。如果用l ( g ) 表示g 的线图,则自然得到兄( g ) = x l ( l ( g ) ) ,根据此性 质和 1 5 ,1 6 l 中部分结论可得下面结果: 定理1 1 设n 是正整数,用r 表示仃阶路,g 表示n 阶圈,则: ( 1 ) 当n 5 时,z ( 只。) = x ( l ( 只。) ) = 3 ( 2 ) 轮3 州( 耻x ( 删= 铲= , 设g ,日是图,保持g 和h 各自的连边关系不变,再将g 的顶点与日的顶点全部连边 构成的图用gvh 表示,称作g 与日的联。 定理1 2 设g ,日是图,则兄( gvh ) sm a x x o ( g ) ,z ( 日) ,+ 麝,其中是g 与h 之 问的连边数。 证明设= m 一 砭( g ) ,x :( 日) ) ,首先将g 和h 都肌星边染色,然后用种新颜色染 剩余的条边,此染法是gvh 的一个+ 肛星边染色,定理得证。 因为z ( k 4 ) = 砭( k 2 v k 2 ) = z ( 鲍) + 4 = 5 ,兄( k 5 ) = x :( 娲v 鲍) = x o ( 蚝) + 6 = 9 ,所以定理1 2 的上界是可达的。在后面我们还证明了也( 凰) = 1 2 ,将蚝看作是两 个娲的联,此结果也符合定理1 2 的上界。下面我们研究完全图的星边染色,常用k 。表 示n 阶完全图。我们先是以确定凰的星边色数为例介绍了一种对确定低阶图的星边色数 有效的方程方法,然后利用性质1 1 和性质1 2 结合定理1 2 的结论分析了n 阶完全图星边 色数的上界。 性质1 4 也( k 6 ) = 1 2 。 证明根据性质1 1 和性质1 2 知9 z ( 凰) s1 3 ,证明的思路是先用反证法证明 了甄不存在1 1 一星边染色,然后给出了甄的一个1 2 一星边染色,从而说明f o ( j “) = 1 2 设x ,( 凰) = 1 1 ,则的一个l l - 星边染色将e c k 6 ) 划分成1 1 个色匹 配置,岛,局1 ,由于凰的最大匹配中只包含3 条边,并且是完美匹配,所以的1 1 个色匹配中至多有一个包含3 条边,下面分两种情况讨论, n ) f e ,玩,置。) 中恰有一个色匹配忍是完美匹配。设只含一条边的色匹配 有z 个,含2 条边的色匹配有9 个,则有方程组 z + 暑21 0 解得; 28 说明只含 i 茹+ 2 y = 1 2i = 2 一条边的色匹配有8 个,含2 条边的色匹配有2 个,取这2 个大小为2 的色匹配中的任意一 个易0 j ) ,最u 易都会产生长为4 的路是2 边染色的。 4 1 星边染色概念及性质 6 ) e l ,岛,e 1 1 中没有完美匹配。山方程组 嚣+ 9 21 1 解得: 霉2 7 【。+ 劫21 5iy 2 4 说明只含一条边的色匹配有7 个,含2 条边的色匹配有4 个,不失一般性, 设毋,岛,e 3 ,毋就是只含两条边的色匹配,任意两个色匹配毋,易( e l ,历,玛,目 ) 的 并最u 毋,要么是一条长为3 的路和一条孤立边,要么是两条不相交的长为2 的 路。对于三个色匹配的并,不妨就取毋,岛,岛研究其性质,首先考虑毋u 助,然 后将玛与毋u 岛并,这样的满足是星边染色的结构有三种( 图l 1 ) : 曲曲曲 圈1 1 毋u 岛u 昂的结构 其中标1 ,2 ,3 的边分别是毋,岛,岛中边,黑色实点表示的是局,历中边的公共 端点。在正常边染色的前提下,不难验证( 且ue 2ue 3 ) u 玫的结构中必然包含长为4 的 路是2 边染色的,所以砭( ) 21 2 。 下面只需要说明凰存在1 2 - 星边染色。设v ( k e ) = 移1 ,v 2 ,v 3 ,啪,v 5 , ,对边e e ( ) 用c ( e ) 表示e 上所染颜色,令c ( t ,i u 6 ) = 1 ,c ( v l v 5 ) = 2 ,c ( v l v 3 ) = 3 ,c ( u i t 2 ) = 4 ,c ( u 2 v 6 ) = 8 ,c ( 忱v 4 ) = 6 ,c ( v 2 v 3 ) = 2 ,c ( v 3 v 5 ) = 7 ,c ( 地铂) = 8 ,c ( v 4 v 6 ) = 9 ,c ( u 4 5 ) = l ,c ( 5 u 6 ) = 5 ,c ( 1 蛳) = 1 0 ,c ( v 2 v 5 ) = 1 1 ,c ( v 3 v 6 ) = 1 2 ,此染色法对应上述方程组的 解茁= 9 ,”= 3 ,是凰的星边染色。 综上所述,z ( k 6 ) = 1 2 ,性质得证 称性质1 4 的证明中用方程求解图的星边色数的方法为方程法。利用方程法很快可 以验证砭( 硒) = 5 ,z ( k s ) = 9 对于低阶完全图,此法可以确定也( ) 的值,但是 当磷2 大时,由于方程的未知变量迅速增加,从而要分析的情况大量增加,导致方程法 不适用。下面给出完全图星边色数的一个界。 触肌邯懒) s 懈i n 2 巾- 2 + 乳1 1 , 孙5 嚣; 证明根据星边染色的定义下界自然成立。对于上界,设n = s + r ,8 r ,根据性 质1 1 知兄( 虬) 兄( 虬) ,因为掣lv g ,由定理1 2 知,砭( j f n ) = z ( 虬vj 0 ) m n z 砭( j ) ,z ( 坼) 卜ps r = 圮( k ) + s r ,利用性质1 2 可得,x :( j o ) s ! = 产一【j r j , 5 1 星边染色概念及性质 所以x 二( j 厶) s 生= 乒一【副+ s r ,当rio ( m o d 2 ) 阼t ,z ( 厩) r 2 + 0 一1 ) r + 1 = - r 2 + ( n - 1 ) r + l ,当r 兰1 ( l d d 2 ) 时,x :( ) 曼i l r 2 + ( r 1 ) + ;= - i t 2 牟( t l 一1 ) r + i 又因为r 2 ,所以当,l ;o ( m o d 4 ) 时,砭( 虬) i 舻一詈+ 1 f 2 萨一2 + 1 1 ,n 为其它 情况时,兄( j 厶) i n 2 一+ 郭,定理得证 容易验证n = 4 ,5 ,6 时,定理1 3 的上界是可达的 定理1 4 设竹是正整数,用j k l 表示仃+ l 阶扇,h ,n + 1 表示n + l 阶轮,则: f 2 , 当肛4 ; ( 1 ) 砭( r + 1 ) = n + 1 , 当,l = 2 ,3 ,5 ,6 ; t n ,当,l 7 f n “ 当肛4 ; ( 2 ) z ( 饵1 ) = n + 2 , 当n = 3 ,5 ,6 ; 【n 当竹7 证明( 1 ) 当,l = 4 时,r 可以看作是山g 和g 内部两条边构成,山定 理1 1 知兄( g ) = 4 ,首先把g 用四种颜色星染色,然后给魄内部两条边染两种新 颜色得到f 5 的一个6 - 星边染色,所以4s 兄( r ) 6 ,利用方程法可验证最不存在5 一星边 染色,所以x :( r ) = 6 当n 4 时,r + l 可以看作是由g + 1 和g + l 内部n 一2 条边构成,由定理1 1 知,此 时砭( g + - ) = 3 ,用三种颜色将g + l 星边染色,g + l 内部的礼一2 条边用n 一2 种新颜色 染好,得到l 的n + 1 - 星边染色,所以ns 感( r + 1 ) 曼几十1 ,当n = 2 ,3 ,5 ,6 时, 可用方程法证明此时兄( r + 1 ) = n + 1 。当地7 时,设r + 1 的最大度顶点是v o ,扇弧 上的顶点从左到右依次为 l ,用c ( e ) 表示边e 上所染的颜色,令c ( v o v | ) = i o = 1 ,2 ,n ) ,c ( 吩+ 1 ) = j + 3 0 = 1 ,2 ,l 一3 ) ,c ( 一2 一1 ) = 1 ,c ( 一i ) = 2 ,得 到l 的一个m 星边染色,结合兄( f - ) 2 仃可证此时砭( r + 1 ) = 竹 ( 2 ) n 为h 0 + 1 = f 1 + 吨,所以在1 星边染色基础上给t ,l 染一种新颜色 即可得到+ - 的星边染色,山于l 是眠+ - 的子图,根据性质t 1 知,z ( f 1 ) x :( w 0 1 ) sx :( 1 ) + 1 ,利用方程法可验证,当n = 4 时,z ( w j ) = 7 ,当n = 3 ,5 ,6 时,砭( w 0 1 ) = 竹+ 2 。当t l 7 时,在上述1 的仔星边染色基础上令c ( m ) = 3 即得到l + 1 的伽星边染色,所以此时z ( w 4 1 ) = n 综上所述,定理得证。 定理1 5 设g 和日是图,则z ( a o h ) r a i n 兄( g ) + i y ( g ) i z ( 日) ,兄( 日) + l 矿( 日) i 兄( g ) ) ,其中go 日表示g 和目的笛卡尔积。 证明根据图的笛卡尔积性质,以g 为主体,可以将g 的每个顶点看作是一个日, 给i v ( a ) 1 个h 染i v ( a ) i 兄( 日) 种颜色,要求每个日使用也( 日) 种颜色染好,并且已使用 6 1 星边染色概念及性质 的颜色在其它日中不出现,而h 的顶点对应的i v ( h ) 1 个g 的同构图另外使用兄( g ) 种新颜 色去染,显然形成一个g o 引构z ( g ) - t - i v c g ) i 砭旧) 一星边染色。如果以日为主体,则 形成一个g o 日的兄( 日) + i y ( h ) i 兄( g ) 一星边染色,定理得证。 对定理1 5 而言,上界可达的一个简单实例就是两个连杆的笛卡尔积。因为超立方 体q k 型q k 一1oj 幻,结合定理1 5 可得砭( q 。) “竹 铲一1 + x :( q k 一1 ) ,1 + 2 兄( q 。一1 ) ) , 这个结果给出了超立方体星边色数的一个递推关系,利用此递推关系可以得到兄( q 。) 2 n 一1 ,在奉文第三节中我们将专门研究超立方体的星边染色并且给了z ( q 。) 一个更好 的上界 受文献【1 5 】中定理1 证明思路的启发,我们得到关于正常边染色与星边染色关系的结 果: 定理1 6 ( 正常边染色与星边染色关系定理) 若图g 的最大度为,则砭( g ) ( + 1 ) 2 a 。 证明由v i z i n g 定理【1 7 l 知,g 有+ 1 正常边染色,设g 的一个+ 1 正常边染色 将g 的边集划分为+ 1 个色匹配舰,m a + t ,刚对任意的i 歹f l ,2 ,+ l 有脱u 毛是一个以路为连通分支的森林,根据性质1 1 ,胍u 易中每条路都是4 - 星 边染色的,对 磊u m j 中的任意一条路p 用颜色 l ,2 ,3 ,4 ) 染,要求进行4 _ 星边染色时 从p 的任意一条边开始,不失一般性,设边e m 是p 中一条边,用c ( e ) 表示e 上所染 颜色,不妨令c ( e ) = 1 ,任意,e ( p ) e ) ,c ( ) = ( d ( e ,) + 2 ) m o d a ,这里d ( e ,) 表 示e 与f 2 _ 闯距离,e 与,邻接时d ( e ,力= 0 ,不难看出此染法是p 的一个4 - 星边染色, 并且m i 中边只染( 1 ,3 ,m j 中边只染 2 ,4 。用g ,j ( e ) 表示j 】l 最u 屿中边e 在4 星边染色时 所染颜色现在定义g 的一个边染色c ,设e e ( g ) ,则e 一定属于某个 毛,令c ( e ) = ( c 1 j ( e ) ,g l l ( e ) ,c i t + 1 ( e ) ,q ,+ l ( e ) ) ,注意q j ( e ) l ,3 ) 或c , j ( e ) ( 2 ,4 ) ,所以 染法c 至多使用t ( a + 1 ) 2 a 种颜色,且c 是正常边染色,假设e 与,在g 中邻接,则e 和,分 别属于不同的色匹配尬和 毛,因此c ( e ) c ( ,) 。 现在我们证明g 中无长为4 的路是2 一边染色的,用反证法,设p 是g 中任意 一条长为4 的路,e ,h ,z 是p 中顺次邻接的4 条边,如果p 是2 一边染色的则c ( e ) = c ( ,1 ) ,c ( ,) = c ( z ) ,说明e ,危属于某个色匹配胍,说明,f 属于某个色匹配坞,所 以c j ( e ) = c , a h ) ,c , a f ) = g u ( f ) ,从而导致p 在 磊u 坞中是2 一边染色的,矛盾- 综上所述,定理得证。 7 2 树的星边染色 本节将研究树的星边染色,我们首先研究了完全 又树的星边染色,证明了存 在实数【1 ,2 】,使得兄( t k ) = 跏+ 1 ,进而证明了对任何最大度为的树t - q - 在实 数e 【1 ,2 】,使得x :( ? ) = 6 。利用这个结果我们还得到了h a l i n 图和单圈图星边色数的 上界 山星边染色的定义知,当树t 中最长路的长度小于或等于3 时,z ( t ) = ( t ) ,下 面我们讨论两个星边色数接近边色数的特殊图类。 定理2 1 若t 1 1 耽 n k ,则x :( & l + l o s 啤+ l o o s + 1 ) = ( 晶1 + 1 0 s k + 1 0 0 & 膏+ 1 ) = n k + 1 ,其中& 。+ 1 0 & 2 + l0 o 。+ l 表示将k 个星的中心依次相连得到 的图,啦2 。 证明设h = r ,+ l os 毛+ 1o o s + l ,因为兄( 日) = 砭( l ( 日) ) ,所以只须考 虑l ( 日) 的星色数,s n 。+ 1 与。+ 1 在l ( 日) 中对应的分别是完全图j 0 ,+ 1 和+ 1 ,其余的 星岛。+ l 1 ,) 对应的是完全图噩h + 2 ,山于n l n 2 ,所以。+ 1 是其中阶 最大的完全图。给l 旧) 这样的顶点染色,首先给。+ 1 染竹k + 1 种颜色 1 ,2 ,- ,n k - i - 1 ) ,要求颜色n k + 1 染在星& 。+ 1 与星一。+ 1 对应的完全图的公共顶点上,然后给 星。+ l 对应的完全图j 厶。+ 2 染色时,山于尬u + i 与j 一。+ 2 的公共顶点已经染颜 色m + 1 ,并且7 1 , k 一1 十2 竹+ 1 ,那么剩余的n k l + 1 个顶点的染色按这样的规律, 将。+ 2 与。+ 2 的公共顶点染颜色m ,其余的一1 个顶点染 l ,2 ,讯一1 ) ,同样 的染色规律依次染下去得到l f 口) 的一个正常顶点染色。现在证明上述染色是星染色 的,首先每个星对应浆j l ( h ) 中的完全图的内部在此染色下没有长为3 的路是2 - 顶点 染色的,因此若l ( 日) 中存在某条长为3 的路是2 顶点染色的,那么它一定包含完全图 之俺j 的公共顶点,但从染色的规律可知,随着礼 逐渐的变小,公共顶点上的所有颜 色只出现一次,从而不会有长为3 的路是2 - 顶点染色的。又因为( ) = ,l k + 1 ,所 以兄( 日) = m + 1 ,定理得证。 定理2 1 的结果说明上述特殊树是一类满足星边色数等于边色数的图。 定理2 2 设t 是树,如果t 中所有度大于等于3 的顶点都在t 的某条路上,则兄( t ) s + 1 ,其中= ( t ) 。 证明设t 中所有度大于等于3 的顶点都在t 的路p 上,注意到总可以保证p 的两个 端点是l 度顶点,因为若p 的端点z 不是1 度顶点,可以选择z 的邻点y ,若”是1 度顶点, 令p = p - i - x y 。若仍然不是l 废顶点,则重复上述操作总能使得尸的两个端点是l 度 8 2 树的星边染色 顶点,并且p 上仍然包含t 中所有度大于等于3 的顶点。现在给出t 的+ 1 星边染 色,首先将p 的边用颜色 n ,6 c 按照三元序( d ,b ,c ) 循环染色,染色从p 的左端点向右 端点的方向进行,山于t 中所有度大于等于3 的顶点都在p 的内部,所以p 的外部顶点 均是l 度或2 度顶点,设是p 的一个内部顶点,则d p ( u ) = 2 ,若而( t ) = k ,则以i f , 为 起点向p 的外部引出k 一2 # a 路,给与i f 关联的非p 中k 一2 条边用k 一2 种颜色正常边染 色设p ,是山t 引出的k 一2 条路中的任一条,将t 看成是p 的起点,此时与t 关联的p 中的一条边已经用k 一2 种颜色中的一种染好,p 中其它边按照从t 到p 终点的方向 染色,如果t 在p 中关联边染颜色n ,b ,则p ,中未染色边用三元序( c ,d ,6 ) 循环染色,如 果硅p 中关联边染颜色抚c ,则p ,中未染色边用三元序( 吼如蹦隋环染色,如果钍在p 中关 联边染颜色口,c ,则p ,中未染色边用三元序( 6 ,c b ) 循环染色,其它山t 引出的路均以此 染法染色,其它p 的内部顶点引出的路也均按此染法染色山于k 茎a ,所以最多使 用一2 + 3 = a + 1 种颜色可完成染色。现说明染色是星边染色的,因为p 是星边染色 的,山p 的内部顶点引出的p 外部的路也都是星边染色的。那么,若有长为4 的路是2 - 边 染色的,则它一定包含p 中边和p 外部边。根据染色的规定知,p 上的任意一条边上所 染颜色与此边距离为l 的边上所染颜色都不同,因此不会有长为4 的路是禾边染色的,定 理得证。 定理2 3 设t 是树,如果( d = a ,则存在实数e 【l ,2 】,使得z ( 即= 。 为了证明定理2 3 我们首先研究完全n 叉树的星边色数。 定义2 1 设n ,是正整数,用。表示最大度为n + 1 的层完全n 叉树,其中第一层只 有一个顶点,对每个i ( 1 i ) 第i 层的每个顶点只能与第i l 层的一个顶点相邻,对 每个,( 1 j t ) 第j 层的每个顶点与第,+ l 层的n 个顶点相邻。 山定义知噩1 是一个孤立点,当竹= 1 ,t 2 时,五t 表示一条长为t 一1 的 路,兄( 7 1 , 2 ) ;1 ,死( t 1 , 3 ) = z ( 霸,4 ) = 2 ,当t 5 时,z ( 乃) = 3 。当n = 2 时,乃3 垡 磊h ,兄( t 2 , 3 ) = 4 ,在砭3 的4 - 星边染色的基础上可以得到x :( 乃,4 ) = 4 实际上,正 4 可 以看作是d t 2 a 添加8 条悬挂边得到的,疋3 的每个第三层顶点都引发出2 条悬挂边,任 选一对有公共端点的未染色悬挂边开始染色,设公共端点是u ,与i f , 相邻的第二层顶 点是 ,染色过程中要求选中的一对悬挂边必须有一条染与 的关联边相异的颜色,因 为d ( 口) = 3 ,颜色总数为4 ,所以必然可以满足这样的染色要求,其它的3 对新添加的 有公共端点的悬挂边也按此规则染色,最终可得n t , 的4 - 星边染色,称此染色方法, 4 为相异染色法,所需最少相异颜色数称为相异染色数。在这个染色规则下可以证明 当t23 时r 兄( 7 2 f ) = 4 9 2 树的星边染色 定理2 4 如果3 ,则: f 4 ,凯_ 2 ; ( 1 ) z ( 黾t ) = 6 ,当n = 3 ; 【7 。当n :4 。 ( 2 ) 存在实数【1 ,2 1 ,使得x :( 死,t ) = 跏+ 1 证明( 1 ) 先证明砭( 乃,t ) = 4 ,用归纳法,根据前面的叙述已经有也( 死t 3 ) = 4 ,兄( 死4 ) = 4 假设当t = 七 5 ) 时x :( 为 ) = 4 ,我们在乃 的4 - 星边染色基础上来构建t 2 朋- t l y j 4 - 星边染色首先,乃 4 - 1 可以山t 2 s 生成,生成的过程是将乃,女的第七层的每一个顶点与 两个新顶点相连,所有新增$ j 2 个顶点恰好是乃“l 第k + 1 层的顶点集合,一个新增的 顶点恰好对应一条新增的悬挂边。乃l 的第k 一1 ,七,k + 1 三层中所有顶点生成的子 图是2 k 一2 个互不连通的乃3 的拷贝,记这些拷贝的集合为f 。因为f 中任意两个元素的新 增边的染色互不影响,所以只要证明f 的某个元素中新增的4 条边仍然可以用t 2 , 用过 的4 种颜色去染,且满足星边染色,那么乃l 就是4 - 星边染色的。任取h f ,h 中包 含了新增的4 条悬挂边,记这4 条悬挂边为h 1 ,j 1 2 ,7 1 3 ,k ,为叙述方便我们给出图示禾l 。 图2 1 :日的图示 注意到e 1 ,e 2 ,e 3 ,e 4 ,e 5 在乃。中已经染好,并且根据相异染色法的要求,e 4 和e s g 然有一个与e 1 ,e 2 ,e 3 的染色都相异,不妨设e 4 与e 1 ,e 2 ,e 3 的染色都相异,给h 1 染8 3 的颜 色,染与8 3 ,e 4 ,e 5 都不相同的颜色,因为总共有4 种颜色,所p a h 2 $ j 染色要求是可以 实现的由于星边染色和颜色总数的限制,e s 必然与e 1 和e 2 其中一个染色一致,所 以蚝和k 不能染8 3 和e 5 上的颜色,这样恰好剩余两种颜色可染蚝和,并且其中一种颜 色与e 3 ,e 4 ,8 5 的染色都相异。 现在说明此染色是星边染色的。首先此染法自然是正常边染色,又因为h l 和h 2 都 与e 5 染色不同,e 4 与e 1 和e 2 的染色不同,所以不会有长为4 的路是2 一边染色的,此 1 0 2 树的星边染色 时日的4 条新增悬挂边染色完成,并且与已染色的而k 结合后仍然是星边染色的,而f 中 元素染色互不影响,所以按照日的染色方法染f 中其它元素可以得到死斛l 的4 星边染 色,所以当t 3 时,兄( 强i ) = 4 回顾图示2 - l ,图示禾l 中要求铂和8 5 必然有一个与8 1 ,e 2 ,e 3 的染色都相异,但是随 着n 的增大,比如乃。在等同e 4 ,e 5 的位置有三条边,在等同e 1 ,e 2 ,8 3 的位置有四条边,我 们发现在6 种颜色染色的情况下,等同,e 5 位置的码j 的三条边可以有两条边与乃j 在 等同e 1 ,e 2 ,e 3 位置的四条边所用颜色相异,也就是说,对死j 相异染色时相异染色数 为1 ,t s j 的相异染色数为2 ,并且五j 的相异染色数也恰好是2 ,使用归纳法同理可证 当t 3 时z ( 墨,) = 6 ,z ( 五j ) = 7 ( 2 ) 首先说明瓦。有2 n + 1 - 星边染色由( 1 ) 的证明知。用2 n + 1 种颜色染2 k 时相异染 色数可以达到n ,根据( 1 ) 的证明思路容易证明t 有加+ l 一星边染色。又因为星边染色 要求正常边染色,自然有n + lsz ( 瓦。t ) ,所以n + 1 砭( 死。) s2 n + 1 ,说明存在实 数【1 ,2 】,使得砭( 露,t ) = s n + 1 综上所述,定理得证。 显然,当n = 1 ,t 5 时e 可以取到2 。 定理2 3 的证明 设t ,y ( t ) 且d ( v ) = a ,将t 看作是以u 为根的树,记v 的邻点为钞1 ,砚,弘,任 意去掉一条边 仉“= 1 ,) 形成分别以 和仇为根的两个不交树咒和咒,不难看 出瓦和瓦。都是完全一l 叉树? 么- 1 。的子图,由性质1 1 和定理2 4 ( 2 ) 的证明知,瓦和瓦都 是2 a 一1 - 星边染色的,再给 仉染种新颜色,显然得到t 的一个2 a 一星边染色,所 以s 兄( t ) 2 ,说明存在实数【1 ,2 】,使得x o ( t ) = e ,至此定理2 3 得证。 利用定理2 4 ( 1 ) 的结果和定理2 3 的证明思路立刻有: 、 f5 ,( t ) - - - - 3 ; 推论2 1 设嚷树,则磁( d 7 ,a ( t ) = 4 ; 【8 ,( t ) :5 。 设t 是树,将丁的所有一度顶点顺次连边形成一个圈c ,山喇c 构成的图称 为h a l i n 图。如果图g 中只有唯一的圈,则称g 为单圈图。山定义不难发现h a l i n 图和 单圈图都是以树为主体结构的特殊图类,利用定理2 3 的结果立刻有下面推论: 推论2 2 设g 是最大皮为的h a l i n 图,则存在实数1 1 ,2 】,使得贬( g ) s + 4 。 证明设h m i n 图g 是由树t 和圈c 构成的,则a ( t ) = a ( c ) = a ,由定理2 3 知,存 在实数【1 ,2 】,使得砭( 砷= e ,山定理1 1 知砭( e ) s4 ,所以将丁用e 种颜色星边 染色,再将e 用4 种新颜色星边染色,此时得到g 的一个+ 4 星边染色,推论得证。 推论2 3 设g 是最大度为的单围图,则存在实数e ( 1s 2 ) 使得兄( g ) 兰e a + 1 。 l l 2 树的星边染色 证明任意去掉g 中圈上一条边e ,则g e ) 是树t ,且( 刃兰a ,山定理2 3 知,存 在实数f l ,2 】,使得砭( t ) se a ,将e 染一种新颜色添加在t 上形成g 的s + 1 一星边染 色,推论得证。 1 2 3 超立方体的星边染色 奉节将研究超立方体的星边染色,利用定理1 5 我们在第一节中已经讨论了超立方 体的星边染色并且证明了n 维超立方体的星边色数2 n 一1 ,通过分析l 维超立方体的结 构,奉节中我们证明了n 维超立方体的星边色数2 u 一2 并且是可达界。 n 维超立方体常用仉表示,q k 的顶点是由2 ,1 个( o ,1 ) n 维向量构成,q 。的两个顶点 相邻当且仅当对应的两1 维向量恰好有一个分量不同山超立方体的定义可知,q l 是 一条孤立边,q 2 笆a 。可将q 2 的2 2 个顶点所对应的2 2 个二维向量转变成三维向量 从而构造q 3 ,具体操作是将每个二维向量在前方空出一位添加0 或1 ,例如( 0 0 ) 转变 成( o o o ) 和( 1 0 0 ) ,要求( o o o ) 除了保持在q 2 中( 0 0 ) 原有的相邻关系外就只与( 1 0 0 ) 相连, 用o q 2 表示保持q 。的相邻关系且在q 2 的所有顶点对应的二维向量前添加元素0 构成的 图。类似的定义l q 2 ,显然o q 2 型1 q 2 竺q 2 ,q 3 = o q 2 + 1 q 2 ,这里“+ ”表示在构 成q 3 的过程中o q 2 和1 q 2 的外部连边按q 。的定义要求的连边规则进行推广到一般情况 有q k + 1 = o q 。+ 1 ( k 。 为叙述方便我们引入一些特殊符号
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- (新教材)人教版小学数学六年级上册第一单元确定位置《用有序数对确定位置》教学课件第1课时
- 初中九年级科学核能的利用与安全防护教学设计
- 初三道德与法治《理性看待“谷子经济”》教学设计
- 高中数学高二年级选择性必修第一册空间直角坐标系中距离问题教学设计
- 八年级美术《从神话到世俗》教学设计
- 高三英语读后续写十三大话题万能模板与情节逻辑教学设计
- 小学三年级科学活字印刷体验教学设计
- 八年级数学教学设计:分式章末复习与核心素养培育
- 七年级语文第六单元预习教学设计
- 高中地理选择性必修一陆地水体相互转化教学设计
- 2026三项岗位人员(应急管理局)-熔化焊接和热切割-焊接与热切割作业(压力焊作业人员)历年参考题库含答案详解
- 宁夏吴忠市盐池县2026年社区工作者招聘考试试卷-含答案解析
- 2026中国洗衣干衣行业市场现状需求分析投资布局发展策略研究文献
- 环境应急预案备案依据(3篇)
- 2026年江西省高考物理试卷真题(含答案及解析)
- 特香型白酒的讲解
- 2026中国邮政社会招聘笔试真题(完整版+详细答案解析)
- 五年级上册《白鹭》课件
- 岩爆的预防及处理培训课件
- 中国电信理工综合类笔试题库
- CSCO非小细胞肺癌诊疗指南(2026版)
评论
0/150
提交评论