（应用数学专业论文）与频道分配有关的两类图染色问题.pdf

山东师范大学硕士学位论文 与频道分配有关的两类图染色问题 陈丽华 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 图的染色问题是图论的主要研究领域之一，是图论研究中很活跃的一个课题 它在组合分析和实际生活中有广泛的应用随着科技的发展，经典的各类染色已经 不能满足要求，于是产生了许多新的染色 设g 是一个无环边的图g 的顶点正常k 染色是指k 种颜色1 ，2 ，k 对于g 的各顶点的一种分配，使得任意相邻的顶点被染上不同的颜色令x ( g ) = r n i n k l g 是k 色可染的) ，称x ( g ) 为g 的点色数，有时简称为色数图g 的边正常k 染色 是指知种颜色1 ，2 ，k 对e ( g ) 中元素的一种分配，使得相邻两条边所染颜色不 同令g ( a ) = m i n k l g 是边k 色可染的) 称为g 的边色数 g r i n g g s 和y e h 引进了l ( 2 ，1 ) 一标号【1 】，它的自然推广是l ( p ，1 ) 一标号【3 】图g 的一个l p ，1 ) 一标号是从v ( a ) 到一个整数集合的映射厶必须满足：对于任意的 顶点u ，t ， ( 1 ) 若c b ( 乱，钐) = 1 ，贝0i 三( u ) 一l ( v ) l p ； ( 2 ) 若d g ( t ，钐) = 2 ，则ll ( u ) 一l ( v ) i 1 图g 的l ，1 ) 一标号在频率分配中有很强的应用背景w h i t t l e s e y e t 等人在文 章【4 】中研究了图g 的第一剖分图的l ( 2 ，1 ) 一标号图g 的第一剖分图s 1 ( g ) 是图 g 通过在每条边上加一个点得到的图s l ( g ) 的l ，1 ) 一标号对应于从v ( a ) ue ( g ) 到一个整数集合的映射，这个映射必须满足： ( 1 ) 图g 的任意两个相邻的顶点得到不同的整数； ( 2 ) 图g 的任意两个相邻的边得到不同的整数； ( 3 ) 图g 的任意一个顶点和它所关联的边得到的整数必须至少相差p 我们把这种映射称为图g 的p ，1 ) 一全标号 一个p ，1 ) 一全标号的跨度1 2 是指最大标号数与最小标号数的差图g 的所 l 山东师范大学硕士学位论文 有0 ，1 ) - 全标号中最小的跨度，称为图g 的0 ，1 ) - 全标号数【2 】，记为碡( g ) 目 前对图的0 ，1 ) - 全标号的研究还比较初步 n 6 d 6 i ch a v e t 和m i n - l iy u 在文章【2 】 中给出了墨( g ) 的平凡的上下界，提出了仞，i ) - 全标号猜想：墨( g ) ( g ) + 印一1 文章【5 】中的泛宽度染色是新提出的另一种在频率分配问题上有很强应用的一 种染色泛宽度染色是对点染色的推广，是对图顶点的一种剖分要求把所有的顶 点剖分成宽度两两不同的i 一宽度箱五，即同一宽度箱五中任两点的距离大于i ， 托中的顶点用同一种颜色来染不同的宽度箱所染的颜色必须两两不同图g 的 泛宽度色数洳( g ) = m i n k l g 是老一泛宽度可染的) 在本文第一章中，我们主要介绍了文章所涉及的一些概念、术语和符号和图染 色问题的发展情况在第二章中，我们研究了图的( p ，1 ) 一全标号，其中包括外平 面图，二部图，正则图，h a i i n 图以及定义的一种新图第三章中研究了图的泛宽 度染色，给出了二部图和m y c i e l s k i a n 一图的泛宽度色数的最好可能上界，给出了 几类特殊图的泛宽度色数 在本文中，我们主要得到如下结论： 定理2 1 4若图g 是一个2 - 连通外平面图，且不含三角形，a ( a ) = 3 ，当 p 3 时，有哆( g ) = p + 3 定理2 2 2 若图g 是一个二部图，非正则，a ( a ) = 3 ，且图g 中包含一个相 邻于两个最大度点的最大度点，则入多( g ) = 5 定理2 2 4 若图g 是一个二部图，非正则，( g ) = 4 ，且图g 的最大度生成 子图g 中包含研，3 ，那么a 多( g ) = 6 定理2 3 1 若p x ( a ) + ( g ) 一2 ，并且图g 是边色数x 7 ( g ) = a ( a ) 的一正 则图，则翟( g ) = x ( g ) + x 7 ( g ) + p 一2 2 定理2 3 2 若g 是一个3 - 正则图并且含有1 - 因子，则有碡( g ) p + 5 山东师范大学硕士学位论文 定理2 3 3 图g 是3 - - 正则图，且x ( g ) = 3 , p 3 ，则墨( g ) p + 4 定义2 4 1 3 s 若对于孓连通平面图g ，去掉g 中某个面向的边界上的所有边 后，g 变成一棵树；并且属于y ( 如) 的所有顶点的度数是3 ，那么把g 称作h a l i n 图属于y ( ，0 ) 的顶点称为g 的外部点，其余的顶点称为g 的内部点 定理2 4 3 图g 是一个3 - 正则h a l i n 图，则5 入多( g ) 6 定理2 4 5 图g 是一个h a l i n 图，且a ( a ) = 4 ，则入多( g ) 6 定义2 5 1g 表示任意一个连通图，其中v ( g ) = u 1 ，睨，一，) g ，表示图 g 的复制图，其中v ( g 7 ) = | t ，i ，呓，吒) 新图d ( g ) 是由图g ，经过下述构造 得到的图：把图g 中的每个顶点和图g ，中所对应的复制点连起来，其中y ( d ( g ) ) = v ( a ) u y ( g ，) ，e ( d ( g ) ) = e ( g ) ue ( g ，) u l 钐i ，口2 呓，嵋，) ，不妨称为双图d ( g ) 定理2 5 1g 表示一个圈，则a t ( d ( c n ) ) = 5 定理2 5 2 对于任意的连通图g ，满足a 多( g ) = a + 4 ，那么双图d ( g ) 的全标 号数a 2 t ( d ( g ) ) 碍( g ) + 1 定理3 1 1 对任意的自然数仇，佗，g m ，n 是二部图，我们有洳( g m ，n ) sm i n m ，佗) + 1 ，并且这个上界是最好可能的 简单图的m y c i e l s k i a n 一图【3 5 】在研究图染色问题的临界性上有重要的应用， 我们这里研究简单图的m y c i e l s k i a n 一图的泛宽度染色 定理3 1 4g 是简单图，且i g i = n m ( g ) 表示g 的m y c i e l s k i a n 一图，则 x p ( m ( g ) ) 死+ 2 并且这个上界是最好可能的 另外我们还研究了一些特殊图类的泛宽度染色 3 山东师范大学硕士学位论文 关键词： ，1 ) 一全标号；全标号数；泛宽度染色；泛宽度色数；二部图；外平 面图；h a l i n 图；m y c i e l s k i a n 一图 分类号：0 1 5 7 5 4 山东师范大学硕士学位论文 t w ok i n d so fg r a p hc o l o r i n gp r o b l e m sr e l a t e dt o t h ech a n n e la s s i g n m e n t c h e nl i h u a s h a n d o n gn o r m a lu n i v e r s i t y , j i n a n ，s h a n d o n g ，2 5 0 0 1 4 p e o p l e sr e p u b l i co fc h i n a a b s t r a c t t h ec o l o r i n gp r o b l e mo fg r a p l l si so n eo fp r i m a r yf i e l d si nt h es t u d yo fg r a p ht h e o - r i e s t h ec o l o r i n gp r o b l e mp l a y sa ni m p o r t a n tr o l ei nt h ec o m b i n a t o r i a lm a t h m a t i c sa n d o u rl i v i n g a st h ed e v e l o p m e n to fs c i e n c e ，t h ec l a s s i c sc o l o r i n g sc a n n o tm e e tt h er e q u i r e - m e r i t ，a n ds o m en e wc o l o r i n g sa r ep r o p o s e d a ( p r o p e r ) k - c o l o r i n go fg r a p hg i sa na s s i g n m e n to fo n eo fkc o l o r st oe a c hv e r t e x i ns u c haw a yt h a ta d j a c e n tv e r t i c e sh a v ed i s t i n c tc o l o r s d e f i n et h ec h r o m a t i cn u m b e r o fga sx ( g ) = m i n k l g r a p hgh a sk - c o l o r i n g s s i m i l a r ，a ( p r o p e r ) k - e d g e - c o l o r i n go f g r a p hg i sa na s s i g n m e n to fo n eo fkc o l o r st oe a c he d g es ot h a tn ot w oa d j a c e n te d g e s h a v et h es a m ec o l o r t h ee d g e - c h r o m a t i cn u m b e ro fg a s ( g ) - - - - - m i n k l g r a p hg h a sk - e d g e c o l o r i n g s g r i g g sa n dy e hi n t r o d u c e dl ( 2 ，1 ) - l a b e u i n g si n 1 】i t sn a t u r a lg e n e r a l i z a t i o n l ( p ，1 ) 一l a b e l l i n g 3 o fag r a p hi sa ni n t e g e ra s s i g n m e n tl t ot h ev e r t e xs e tv ( c ) s u c h t h a 七： ( 1 ) l l ( u ) 一l ( u ) l p ，i fd c ( u ，勘) = 1 ； ( 2 ) l l ( u ) 一工( 口) i 1 , i fd g ( u ，影) = 2 。 三国，1 ) 一l a b e l l i n go fag r a p hp l a y sa ni m p o r t a n tr o l ei nt h ef r e q u e n c ya s s i g n m e n t w h i - t t l e s e ye ta 1 i n 【4 】s t u d i e dl ( 2 ，1 ) - l a b e l l i n g so ff i r s ts u b d i v i s i o no fag r a p hg t h ef i r s t s u b d i v i s i o no fag r a p hgi st h eg r a p hs l ( c ) o b t a i n e df r o mg b yi n s e r t i n go n ev e r t e x a l o n ge a c he d g eo fg a nl ，1 ) - l a b e l l i n go fs l ( g ) c o r r e s p o n d st oa na s s i g n m e n to fi n - t e g e r st ov ( c ) ue ( c ) s u c ht h a t ： 5 山东师范大学硕士学位论文 ( 1 ) a n yt w oa d j a c e n tv e r t i c e so fg r e c e i v ed i s t i n c ti n t e g e r s ； ( 2 ) a n yt w oa d j a c e n te d g e so fg r e c e i v ed i s t i n c ti n t e g e r s ； ( 3 ) av e r t e xa n de d g ei n c i d e n tr e c e i v ei n t e g e r st h a td i f f e rb ya tl e a s tpi na b s o l u t e v a l u e w ec a l ls u c ha na s s i g n m e n ta ，1 ) 一t o t a ll a b e l l i n go fg t h es p a n 2 o fa 函，1 ) 一t o t a ll a b e l l i n gi st h em a x i m u md i f f e r e n c eb e t w e e nt w ol a - b e l s t h em i n i m u ms p a no fa 白，1 ) 一t o t a ll a b e l l i n go fgi sc a l l e dt h e ( p ，1 ) 一t o t a ln u m b e r 2 a n dd e n o t e db y 入孑( g ) n o wt h es t u d yo ft h e 函，1 ) 一t o t a ll a b e l l i n gi sn o te n o u g h i nt h e p a p e r 2 ，t h et r i v i a l i t yl o w e ra n du p p e rb o u n d sa r eg i v e na n dt h e ( p ，1 ) - t o t a ll a b e l l i n g c o n j e c t u r e ：a f t ( g ) ( g ) + 2 p 一1 t h ep a c k i n gc o l o r i n g s i sp r e s e n t e dw i t ht h ea p p l i c a t i o nt of r e q u e n c ya s s i g n m e n t s r e c e n t l y t h ep a c k i n gc o l o r i n gi sav a r i a t i o no ft h ec o l o r i n g ，a n dap a r t i t i o no ft h eg r a p h v e r t i c e s a no ft h ev e r t i c e ss h o u l db ep a r t i t i o n d e di n t ot h ep a c k i n g s 托w i t hp u i r w i s e d i f f e n tw i d t h s ，s ot h a ti nt h es a m ep a c k i n g 五t h ev e r t i c e sm u s tb ep a i r s e a td i s t a n c e m o r et h a nia n db ec o l o r e dw i t ht h es a m ec o l o r i n g t h ed i f f e r e n tp a c k i n g sm u s tb ec o l - o r e dw i t hd i f f e r e n tc o l o r i n g s t h ep a c k i n gc h r o m a t i cn u m b e r 洳( g ) = m i n k l g r a p hg h a sk - p a c k i n gc o l o r i n g t h ef i r s tc h a p t e ro ft h i sp a p e rg i v e st h eb a s i cc o n c e p s ，t e r m i n o l o g i e sa n ds y m b o l e s w h i c ha r eu s e di nt h i sp a p e ra n dab r i e fi n t r o d u c t i o na b o u tt h ed e v e l o p m e n to ft h eg r a p h c o l o r i n g i nt h es e c o n dc h a p t e r ，w es t u d yt h e ，1 ) - t o t a ll a b e l l i n go fg r a p h ss u c ha so u t - e r p l a n a rg r a p h ，b i p a r t i t eg r a p h ，r e g u l a rg r a p h ，h a l i ng r a p h i nt h e t h i r dc h a p t e r ，w es t u d y t h ep a c k i n gc o l o r i n go fg r a p h t h eb e s tp o s s i b l eu p p e rb o u n d so nt h ep a c k i n gc h r o m a t i c n u m b e ro ft h eb i p a r t i t eg r a p ha n dm y c i e l s k i a n - g r a p ha r eg i v e n f i n a l l yt h ep a c k i n g c h r o m a t i cn u m b e r so fs o m ep a t i c u l a rg r 印h sa r eg i v e n i nt h i sp a p e rw eh a v et h ef o l l o w i n gt h e o r e m s ： t h e o r e m2 1 4l e tgb ea2 - c o n n e c t e do u t e r p l a n a ra n dt r i a n g l e f r e eg r a p hw i t h ( g ) = 3 , i f p 3 , t h e n 碍( g ) = p + 3 6 山东师范大学硕士学位论文 t h e o r e m2 2 2l e tgb ea b i p a r t i t eg r a p hw i t ha ( c ) = 3 , n o tr e g u l a r ，i fg c o n - t a i n sav e r t e xw i t hm a x i m u md e g r e ew h i c hi sa d j a c e n tt ot w ov e r t i c e sw i t hm a x i m u m d e g r e e ，t h e n 曙( g ) = 5 t h e o r e m2 2 4l e tgb ea b i p a r t i t eg r a p hw i t ha ( g ) = 4 , n o tr e g u l a r ，i ft h ei n - d u c e dg r a p hg o ft h ev e r t i c e sw i t hm a x i m u md e g r e ec o n t a i n s 硒，3 ，t h e na 多( g ) = 6 t h e o r e m2 3 1l e tgb eaa - r e a tg r a p h ，i fp x ( g ) + ( g ) 一2 ，a n d ( g ) = ( g ) ，t h e n 墨( g ) = x ( v ) + x ( g ) + p 一2 t h e o r e m2 3 2i fgi sa3 - r e g u l a rg r a p hw i t h1 - f a c t o r ，t h e n 翟( g ) p + 5 t h e o r e m2 3 3l e tgb ea 3 - r e g u l a rg r a p h ，i fx ( a ) = 8 ，p 3 , t h e n 疆( g ) p + 4 d e f i n i t i o n2 4 1 【3 8 1f o ra3 - c o n n e c t e dp l a n eg r a p hg ( v , e ，f ) ，i fa l le d g e so nt h e b o u n d a r yo fo n ef a c e 0o ft h ef a c es e tfa r er e m o v e d ，i tb e c o m e sat r e e ，a n dt h ed e g r e eo f e a c hv e r t e xo fy ( f 0 ) i st h r e e ，t h e ng r a p hgi sc a l l e dah a l i ng r a p h ，t h ev e r t i c e so ny ( f o ) a r ec a l l e de x t e r i o rv e r t i c e so fg ，a n dt h eo t h e r si n t e r i o rv e r t i c e so fg t h e o r e m2 4 3i fgi sa3 - r e g u l a rh a l i ng r a p h ，t h e n5 a 手( g ) 6 t h e o r e m2 4 5i fgi sah a l i ng r a p hw i t ha ( g ) = 4 , t h e n 入多( g ) 6 d e f i n i t i o n2 5 1l e tgb eac o n n e c t e dg r a p h ，w i t hv ( a ) = 钐l ，v 2 ，) l e t g ，b eac o p yo fgw i t hv ( a 7 ) = i ，呓，吒】an e wg r a p hd ( g ) i sd e f i n e da s f o l l o w i n g s ：v ( d ( g ) ) = v ( a ) uy ( g ，) ，a n d e ( d ( c ) ) = e ( g ) ue ( g 7 ) u 移l 御i ，抛u 5 ， 秽，l 嵋，) ，w ec a l li td o u b l eg r a p hd ( g ) t h e o r e m2 5 1l e tqb ea c y c l e ，t h e nx t ( d ( c n ) ) = 5 t h e o r e m2 5 2l e tgb eac o n n e c t e dg r a p h ，w i t h 入；( g ) = a + 4 , d ( g ) b et h e d o u b l eg r a p hg a i n e db yg ，t h e na t ( d ( g ) ) 久多( g ) + 1 7 山东师范大学硕士学位论文 t h e o r e m3 1 1l e tg m ，nb ea b i p a r t i t eg r a p h ，t h e n 洳( g m ，n ) m i n m ，佗) + 1 , a n d t h i su p p e rb o u n di sb e s tp o s s i b l e m y c i e l s k i a n g r a p h 3 5 】o fs i m p l eg r a p hp l a y sa ni m p o r t a n tr o l ei nt h es t u d yo ft h e c r i t i c a lp r o p e r t yo fg r a p h c o l o r i n g h e r ew es t u d yt h ep a c k i n gc o l o r i n go fm y c i e l s k i a n g r a p h t h e o r e m3 1 4l e tgb eas i m p l eg r a p h ，a n di g i = 佗m ( a ) b et h e m y c i e l s k i a n g r a p h o fg ，t h e nx p ( 彳( g ) ) 几+ 2 a n dt h i su p p e rb o u n di sb e s tp o s s i b l e i na d d i t i o n ，w ea l s os t u d yt h e t h ep a c k i n gc o l o r i n go fs o m ep a r t i c u l a rg r a p h s k e yw o r d s ：( p ，1 ) 一t o t a ll a b e l l i n g ；( p ，1 ) 一t o t a ln u m b e r ；t h ep a c k i n gc o l o r i n g ； t h ep a c k i n gc h r o m a t i cn u m b e r ；b i p a r t i t eg r a p h ；o u t e r p l a n a rg r a p h ；h a l i ng r a p h ； m y c i e l s k i a n - g r a p h 8 c l a s s i f i c a t i o n ：0 1 5 7 5 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意 学位论文作者签名：际一疗年 导师签字：否 、磊 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅本人授权学校可以将学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 学位沦文作者签名：陈硒华 签字日期：2 0 0 7 年舻月l e t 导师签字：翟、磊 签字日期：2 0 0 罗年钐月2 日 山东师范大学硕士学位论文 1 1基本概念与符号 第一章引言 一个图g 是指一个有序对g = ( y ( g ) ，e ( g ) ) 其中v ( a ) 是顶点集，e ( g ) 为 边集，e ( c ) 中的边为y ( g ) 中两不同顶点的无序对若v ( c ) 中的两顶点仳，t ，之 间有边，则称两顶点相邻且互为邻点，边记为删，称边伽关联t ，t ，边删的端点 为牡，u 若两边有公共端点，贝! j 称两边相邻且互为邻边端点重合为一点的边称为 环；若两边有相同的两个端点，则称它们为多重边一个图为简单图，若它既没有 环也没有多重边本文所讨论的图均为简单有限图 y ( g ) 的子集s 称为独立集，若s 中的任意两顶点均不相邻顶点数最多的独 立集称为g 的最大独立集，顶点个数称为独立数，记为a ( g ) 简单图g 的一个团是 指顶点集的一个子集s ：使得g 嘲是完全图顶点数最多的团称为g 的最大团，顶 点个数称为g 的团数，记为u ( g ) 对任意钞y ( g ) ，d ( v ) 表示顶点口在g 中关联的 边数，称为钞的度定义艿( g ) = m i n d ( v ) l 御y ( g ) ) ，a ( c ) = m a x d ( v ) l 口y ( g ) ， 分别称为g 的最小度和最大度 所有顶点均两两相邻的简单图称为完全图，几个顶点的完全图记为设 ，场是图g 的两顶点独立集，若v ( a ) = u ，n k = 口，且图g 的每条边一个 端点在中，一个端点在中，则称g 为二部图或偶图进一步，若中的每 个顶点与中的每个顶点相邻，则称g 为完全二部图，此时若i i - 佗，i 场l - m ， 则记为舢 设图g 为一个简单连通图， 1 ，2 ，3 ，忌) 为一个色集合，若c 是个从v ( c ) 到集合 1 ，2 ，3 ，七) 的映射，即v ( a ) _ 1 ，2 ，3 ，七) ，满足任意相邻的点影，口7 v ( c ) 有c ( 勘) c ( ) ，则称c 为的一个正常k 一点染色且称x ( g ) = m i n kj g 是七 可染的) 为g 的点色数 设图g 为一个简单连通图， 1 ，2 ，3 ，七) 为一个色集合，若c 是一个从e ( g ) 到集合 1 ，2 ，3 ，七) 的映射，即e ( c ) 一 1 ，2 ，3 ，七) ，满足任意相邻的边e ，e 7 e ( g ) 有c ( e ) c ( e 7 ) ，则称c 为的一个正常k 一边染色且称( g ) = m i n k i a 是k 边可染的为g 的边色数 9 山东师范大学硕士学位论文 设g 为一个阶至少为2 的简单连通图，k 是一个正整数， 1 ，2 ，3 ，七) 为一 个色集合，c 是v ( a ) u e ( g ) 到【1 ，2 ，3 ，后 的映射，如果 ( 1 ) 对v u v ，钐伽e ( g ) ，u w ，有c ( u v ) c ( v w ) ； ( 2 ) 对u 口e ( g ) ，有c ( u ) c ( 口) c ( u v ) ； 则称c 为g 的一个k 一正常全染色且称x t ( g ) = m 饥 后i g 是k 可全染的) 为g 的全色数 设g 是一个简单图，对于任意两个顶点z ，y ，他们的距离d ( x ，y ) 是z y 路长 的最小值特别的，如果没有z y 路，则d ( z ，y ) = 本文所用符号与术语基本与文献阻，3 5 】中一致，本节未介绍的其它图论术 语，将在必要时予以阐述 1 2图染色问题 1 7 3 6 年是图论的历史元年，这一年e u l e r 研究了著名的柯尼斯堡七桥问题，发 表了图论的首篇论文，开创了图论科学的研究1 9 3 6 年，匈牙利著名的图论学家 k o n i g 发表了有限图与无限图理论，这是图论的第一部专著，它总结了图论二 百年的主要成果，是图论的重要里程碑此后，图论开始飞速发展起来，成长为数 学科学中一门独立学科 1 9 世纪中叶，四色问题以猜想形式提出来，这个猜想是说平面上任何一个地图 都能够只用4 种颜色给各个国家染色，使得任何两个相邻的国家有不同的颜色，两 个国家相邻是指它们有一段公共边界四色猜想的提出开启了染色问题的研究 图染色问题本质上是对给定图的元素( 顶点，边，面) 依据特定的规则的一种剖 分，因为我们通常把剖分过程看成给每一个元素都安排一种颜色的过程，所以被称 为染色任何图染色问题都包含三个要素：需要染色的元素，加在颜色上的限制及 加在剖分上的限制各个要素或要素之间的组合的不同，我们可以得到多种染色问 题染色问题分为边染色，点染色，全染色以及根据不同要求的其它染色图的染色 理论的基本问题是确定它们相应的色数，而图的色数与图的阶，边数，最大度以及 点独立数等参数有着十分密切的联系目前，随着图的染色问题在现实中的广泛应 用，它逐渐成为众多学者研究的重要领域之一对图的不同染色问题的研究，已有 了较为丰富的结果，并且这些结果仍在进一步完善之中在图的染色问题的研究上 出现最早的是面染色及随后出现的点染色和边染色，这也是最古典的染色问题 在点染色方面，最经典的结果是1 9 4 1 年由b r o o k s 给出的：若是连通的简单图， 并且它既不是奇圈，又不是完全图，则x ( a ) a ( g ) 在边染色方面，1 9 6 4 年v i z i n g 1 0 山东师范大学硕士学位论文 也得到了个重要定理：对于任何简单图g ，有) ( 7 ( g ) = a ( c ) 或x 7 ( g ) = ( g ) + 1 继图的点染色，边染色及组合地图的面染色之后，伊朗数学家在1 9 6 5 年提 出了全染色概念，同年又在其博士论文中提出了一个猜想：对于任意简单图g ，有 x t ( g ) ( g ) 4 - 2 后来人们称之为全染色猜想目前为此，全染色猜想仍是一个 未解决的问题，大量研究全染色的工作，还仅限于全染色猜想的正确性 在传统的点染色，边染色，全染色的基础上附加各种条件限制，近二十年来又 提出了许多种新的染色，例如强染色，邻点可区别边染色，邻点可区别全染色 图染色问题有很强的应用背景生活及科学领域中许多问题的数学模型都可以 用图的形式来建立，然后对图中某些对象按照一定规则进行剖分，而所谓染色只是 对其中剖分方法的一种简单而直观的表达方式，所以染色问题是解决诸如时间表问 题，排序问题，排课表问题，交通状态，运输安排，电路设计和贮藏问题等涉及任 务分配的实际问题的基本方法再者，图染色理论在离散数学领域有着非常重要的 地位，其中许多貌似无关的问题都可以转化为图染色问题因此， t r j e n s e n 和 b t o r t 断言：图染色理论在离散数学中处于中心地位近年来，关于图染色问题的 研究得到了许多有趣而实用的结果，同时又拓展出一些新的染色分支 在频率分配问题中，图染色有很强的应用本文研究的两种染色问题，是从不 同的角度来解决频率分配中遇到的问题我们常常会遇到这样的问题：如果两个传 输站点的距离很近时，那么它们所传输的信号容易发生干扰因此距离比较近的站 点传输的信号的频率必须不同，对于距离非常近的站点来说，它们传输的信号的频 率必须相差很大才可以 我们用一个整数来代表站点所传输的信号的频率，可以假设分配给每个站点 的信号频率对应着一个整数为了避免干扰，距离非常近的两个站点所得到的信号 频率对应的整数必须相差2 ；进而，对于距离近的但不是非常近的两个站点所得到 的信号频率对应的整数必须不同基于上述问题，g r i n g g s 和y e h 在【1 】中引进了 l ( 2 ，1 ) - 标号它的自然推广是己0 ，1 ) 一标号【3 】 定义1 【2 】图g 的一个l 0 ，1 ) 一标号是从v ( c ) 到一个整数集合的映射厶必须 满足：对于任意的顶点u ，u ( 1 ) 若d g ( u ，钞) = 1 ，则ii ( u ) 一l ( v ) i 烈 ( 2 ) 若d g ( 仳，t ，) = 2 ，贝0ll ( u ) 一l ( v ) i 1 很多文章中研究了这种标号，在文章【3 】中研究了弦图的l ( p ，1 ) 一标号，特别 的w h i t t l e s e y e t 等人在文章【4 】中研究了图g 的第一剖分图的l ( 2 ，1 ) 一标号图g 1 1 山东师范大学硕士学位论文 的第一剖分图s l ( g ) 是图g 通过在每条边上加一个点得到的图8 1 ( g ) 的l p ，1 ) - 标号对应于从v ( a ) ue ( g ) 到一个整数集合的映射，这个映射必须满足； ( 1 ) 图g 的任意两个相邻的顶点得到不同的整数； ( 2 ) 图g 的任意两个相邻的边得到不同的整数； ( 3 ) 图g 的任意一个顶点和它所关联的边得到的整数必须至少相差p 我们把这种映射称为图g 的0 ，1 ) 一全标号 定义2 【2 】一个p ，1 ) 一全标号的跨度是指最大标号数与最小标号数的差图g 的所有，1 ) 一全标号中最小的跨度，称为图g 的，1 ) 一全标号数，记为a 孑( g ) 目前对图的0 ，1 ) 一全标号的研究还比较初步 f r 4 d 4 i ch a v e t 和m i n - l iy u 在 文章【2 】中给出了碍( g ) 的平凡的上下界，提出了0 ，1 ) 一全标号猜想：入；( g ) z x ( g ) + 2 p 一1 文章【5 】中研究了围长和最大度都很大的平面图的全标号数，满足 a ；( g ) ( g ) + 2 p 一2 文章 6 】中作者研究了当p = 2 时外平面图的全标号数 2 0 0 7 年b b r e 吝a r 等人在文章【5 】中新定义的泛宽度染色问题是图染色问题在频 率分配问题上的另一个应用在一个给定的网络中，相邻两个站点的信号会互相干 扰因此相邻的站点需要分配不同频率的信号而信号传播的距离与这些信号的功 率直接相关因此对于距离近的不相邻的站点，可以分配小功率的信号，而对于距 离较远的站点分配功率大的信号 定义1 【5 】g = ( y ( g ) ，e ( g ) ) ，d 是一个正整数，x 是v ( c ) 的一个子集，如果x 中任意两个点的距离都大于d ，称x 是一个宽度箱，d 叫做x 的宽度显然，d 一 宽度箱也是( d 一1 ) 一宽度箱，( d 一2 ) 一宽度箱等等 泛宽度染色要求把所有的顶点剖分成宽度两两不同的t 一宽度箱五，即同一宽 度箱五中任两点的距离大于i 五中的顶点要求染相同的颜色 k 定义2 【5 】给定图g = ( y ( g ) ，e ( g ) ) ，使得v ( g ) = 【j 噩，且墨 = 1 k ) 是 i = 1 v ( g ) 的宽度两两不同的宽度箱的最小整数k ，这个整数k 叫图g 的泛宽度色数， 记作洳( g ) 图g 的一个大小为洳( g ) 的染色叫x p ( g ) 染色显然，此处我们的目 的是最小化k ，可以假设对每个i ，五是一个i 一宽度箱 文献【5 】中作者猜想泛宽度染色问题是p 问题，并给出了无限正六边形和完 全图k 。的剖分图s ( j 靠) 的泛宽度色数在文献【6 】中s l o p e r 研究了树的泛宽度色 数，证明了无限3 一正则树的泛宽度色数为7 ；文献【7 】中给出了无限方格日的泛宽 度色数的下界x p ( 日) 2 2 1 2 山东师范大学硕士学位论文 第二章图的( p ，1 ) 全标号 l ( 2 ，1 ) 一标号来源于频率分配问题，它的自然推广是l ( p ，1 ) 一标号图g 的第 一剖分图s 1 ( g ) 的l ( p ，1 ) 一标号构成了图g 的p ，1 ) 一全标号我们研究了2 连通 外平面图，二部图，正则图，h a l i n 图等不同图类的的( p ，1 ) 一全标号 2 1 外平面图的( p ，1 ) 全标号 本节中我们主要研究了二连通外平面图的( p ，1 ) 一全标号 引理2 1 1 【2 】若p a ，则有墨( g ) + p 引理2 1 2 【2 】对于任意的图g ，有墨( g ) x ( g ) + x ( g ) + p 一2 引理2 1 3 【9 】每个2 - 连通外平面图g ，其中a ( g ) = 3 则g 有偶数个3 度点 定理2 1 4 若图g 是一个二连通外平面图，且不含三角形，a ( c ) = 3 ，当p 3 时，有翟( g ) = p + 3 证明：因为p 3 = a ( g ) ，由引理2 1 1 知入吾( g ) + p = p + 3 下证碍( g ) p + 3 令g o u t 代表g 的外平面，显然g 包含一个哈密顿圈6 ( 蛳) 令x 0 ，z 1 ，代 表g 的所有3 度点，并且在6 ( 蛳) 上以顺时针方向排列只，i = 0 ，1 ，m 代表 6 ( ) 上从以到z 件1 的顺时针方向的路因此若只上除了瓤，x i + i 外还有别的顶 点，那么这些顶点的度数为2 按下述步骤，给出一个映射c ：v ( g ) u e ( g ) 一 o ，1 ，2 ，p + 3 ) 第一步，先来给所有的3 度点x 0 ，x l ，来标号 令c ( x o ) = o ，c ( x 1 ) = 1 ，c ( x 2 ) = 0 ，