（运筹学与控制论专业论文）图的边覆盖染色及分数边染色.pdf

山东大学博士学位论文 图的边覆盖染色及分数边染色 王纪辉 f 山东大学数学与系统科学学院，济南2 5 0 1 0 0 ) ( 指导教师： 刘桂真 教授) 中文摘要 图的染色理论是图论中的一个重要分支图的染色种类有很多，诸如边染 色、点染色、面染色和全染色等其中研究最多，结果也较完善的就是图的边 染色图的正常的边染色就是把图的边集分解为一些互不相交的边的独立集的 并的方法在图的正常边染色理论中有著名的v i z i n g 定理，而其中关于正常边 染色的图的分类问题_ 直是研究的热点近年来，人们开始考虑把图的边集分 解为其它形式，得到一些推广的边染色并进行研究本文主要是讨论了图的边 覆盖染色，一边覆盖染色、分数边覆盖染色和分数边染色等 我们用g ( v e ) 表示一个图，其中y 是顶点集，e 是边集设s 是一个集 合，l s i 表示集合s 的基数在本文中我们所说的图通常指有限简单图如果图 g 中允许有重边则称g 为重图对图g 中的点口，用d g ( 钉) 表示顶点t ，的度，用 r g ( ) 表示t ，的邻点集记6 ( a ) = n f i n d a ( 口) ：钉矿( g ) ) ，a ( g ) = m a x d a ( 钉) ： t ，y ( g ) ) ，则6 ( a ) 和( g ) 分别表示图g 的最小度和最大度在不产生混淆 的情况下，我们常用ke ，( ) ，正a 分别代替y ( g ) ，e ( g ) ， b ( 口) ，6 ( g ) ，a ( g ) 令瓯表示图g 中由最小度点导出的子图如果( g ) = 6 ( g ) = d 则称g 是出正则图，通常也称3 正则图为立方图如果图g 的顶点集可以划分为两个 互不相交的子集和且g 的任何一条边的两个端点分别在和k 中，则 称图g 为二部图若图g 中存在一点u 使得g u 是一个具有二划分为( x ，y ) 的二部图则称g 为近似二部图，记为a ( x ，y ；“) 一个圈是指图中每个点的度 都是2 的连通图，称含有奇数条边的圈为奇圈，含有偶数条边的圈为偶圈 我们用正整数1 ，2 ，来表示颜色，若c 是边集e 到集合 1 ，2 ，七 的 映射，即c ：e 一 1 ，2 ，耐，则称c 为图g 的肛边染色令a ( t ，) 表示在 图g 的在染色c 中与顶点钉关联的染i 色边的数日假定对y 中每个顶点口 都已赋以正整数，( 口) 且要求1 ，( ) d ( v ) 若染色e 使图g 中任意顶点 v 和t 1 ，2 ，舛，都有a ( 口) ，( ) 成立，则称e 为图g 的，- 边覆盖 山东大学博士学位论文 染色能对图g 进行，- 边覆盖缸边染色的最大颜色数k ，称为图g 的户边 覆盖色数，记为z ，o ( g ) 令 ， ，。d ( v ) 。， o ，22 步t l 7 葡j ， 其中【篱j 是指不大于器的最大整数已知 0 1 x ；。( g ) 毋 由上面的式子知，图g 的，_ 边覆盖色数x k ( g ) 要么等于以一1 ，要么等于毋， 由此我们根据x 么( g ) 把图分为两大类：若缘( g ) = 白则称g 是gj 类的，否 贝4 称g 是oj - j 类的若对所有的顶点t ，都满足，( 口) = 1 ，此时以= 6 ，则图 g 的产边覆盖染色就是通常讨论的一般的边覆盖染色对图g 进行边覆盖染色 所需的最大颜色数( 求最小没有意义) 称为图g 的边覆盖色数，记为疋( g ) 类 似的，对于边覆盖染色同样也有分类问题，即若砭( g ) = 6 则称g 是c i 类的， 否则称g 是c i i 类的对于正则图而言，其边覆盖染色的分类问题等价于正 常的边染色分类问题因此，边覆盖染色的分类问题也是p - 完全的对任意 的图讨论它的边覆盖染色分类是很困难的，但对一些特殊图讨论其分类是可能 的讨论图的分类问题时，。临界”的概念是很重要的设g 是连通的非完全图 且z ，o c g ) = 毋一1 ，如果对任意的u ，钉v ，e = 伽隹e 都有玩( g - i - e ) = 毋 成立，则称g 是，边覆盖临界的同样，若对所有的顶点t 7 取，( ) = l ，则 有边覆盖临界图的概念而研究产边覆盖临界图( 或边覆盖临界图) 的性质与 构造对于解决图的基于户边覆盖染色( 或边覆盖染色) 的分类问题具有重要意 义 另一方面，分数边覆盖染色和分数边染色也是近几年出现的新的研究方向 而且，分数边覆盖色数和分数边色数分别对讨论图的边覆盖染色分类和正常边 染色分类有重要的作用因此，讨论图的分数边覆盖染色和分数边染色也是非 常有意义的 图g 的分数边覆盖染色是指给g 的每一个边覆盖c 分配非负权，使 得对任意的e e ( v ) 满足c b e u cs1 ( 其中g 。是对含边e 的g 的所有 的边覆盖求和) ，相应的分数边覆盖色数x f ( g ) 是指可进行分数边覆盖染色的 c ( 是对g 的所有的边覆盖c 求和) 的最大值 类似地，图g 的分数边染色是指给g 的每一个边匹配m 分配非负权f d m 。 使得对任意的e e ( g ) 满足m g e “，膨1 ( 其中m ，。是对含边e 的g 的 山东大学博士学位论文 所有的匹配求和) ，相应的分数边色数x ( g ) 是指可进行分数边染色的mu m ( 是对g 的所有的匹配m 求和) 的最小值 关于图的边覆盖染色的结论与图的正常边染色的结论有很多是类似，但是 其本质上有很大的不同，很多结论无法从正常边染色的结论中推出来对二者 进行研究所用的方法和手段也有很大的不同，其研究足相对独立的 本文分为五章第一章介绍了图论的基本概念和边染色的历史和发展状况， 给出了一个简短但相对完整的综述第二章讨论了边覆盖染色的分类，首先是 给出一般图是c ，或c i i 类图的一些充分条件，然后又对某些特殊图的分类进 行了讨论得到一些有意义的结果，最后对边覆盖临界图的性质和构造进行了讨 论，给出了一种构造边覆盖临界图的构造方法第三章我们首次对，- 边覆盖染 色的分类和，一边覆盖临界图的性质进行了研究，得到许多比一般的边覆盖染色 更强的一些结果在第四章首先介绍了分数边覆盖色数的定义并在原有结果的 基础上给出了一个更为精确的分数边覆盖色数计算公式还讨论了分数边覆盖 色数和边覆盖色数的关系，对于图的边覆盖染色的分类有重要意义第五章我 们首先介绍了分数边色数的定义并讨论了特殊图的分数边色数，对于图的正常 边染色中某些猜想我们还讨论了其在分数边染色中的正确性 下面列出本文的主要结果 结论1 设g 是最小度为2 的图，则g 是c i i 类的当且仅当g 是奇圈。 结论2 设图g 的最小度为6 ，如果g 的由最小度点导出的子图g 是孤 立点集，则图g 是e ，类的 结论3 设a ( x ，y ； ) 是近似二部图且最小度623 ，若d ( u ) 2 6 1 ，则 a ( x ，y ；u ) 为e j 类的 结论4 设a ( x ，y ；) 是近似二部图且最小度623 ，若邻点集 r g ( “) 中至 多含一个最小度点，则a ( x ，y ；仳) 为c j 类的 结论5 设a ( x ，y ；“) 是近似二部图且最小度d 3 ，s = 扣n a ( u ) l d ( v ) = 升若满足s x 或s y 且d ( u ) 6 + l s 卜1 ，则g ( x ，y ；u ) 为c f 类的 如果在g 中存在点t ，满足d ( v ) = 毋，( 口) ，则称口为西一点显然，( t ，) = 1 m 山东大学博士学位论文 时，0 一点就是最小度点令 y 邓：乃= 【端j , v e v ) ，w 邛：毋= 器艇 结论6 设g 是一个图，( 口) 和旷如上述定义如果对所有的点矿v + ， 有f ( v ) 十d ( v ) ，则g 为qj 类图 结论7 设g 是一个图，( ”) ，砖和w 如上述定义如果由w 中的点 导出的子图是孤立点集，则g 为c ，j 类图 结论8 设g 是一个礼阶完全图如果对任意t ，v 有，( 口) = k ，k id ( v ) 且知和n 都是奇数，则g 为qj ，类图否则，g 为oj 类图 结论9设g 是一个，- 边覆盖临界图则对任意的u ，t ，v 且e = 删 e ，必存在伽u ，t ，) 满足d ( 叫) 毋( ，( 伽) + 1 ) 一2 使得叫至少与d ( 伽) 一曲，( 伽) + 1 个6 ，一点相邻 结论1 0设g 是一个图，则其分数边覆盖色数为 姻叫g ( g ) = 唾n 鼢 其中s 是y ( g ) 的任意非空子集且满足i s i 是奇数，e 翻表示至少有一个端点 在s 中的边集 结论1 1 设g 是一个图，则6 1 ；( i y ( g ) l 一3 ) ，和 ( 2 ) g 的由最大度点导出的子图g 么的最小度至多是1 则彤( g ) = a 关键词：边覆盖染色；产边覆盖染色；分数边覆盖染色；分数边染色； 色数；边覆盖临界图；图的分类 山东大学博士学位论文 e d g ec o v e rc o l o r i n ga n df r a c t i o n a le d g e c o l o r i n go fg r a p h s _ 、v v a n g & h u i ( s c h o o lo fm a t h & s y s s c i ，s h a n d o n gu n i v ，j i n a n2 5 0 1 0 0 ) a b s t r a c t t h ec o l o r i n gt h e o r yo f 口a p l l si so n ei m p o r t a n tb r a n c ho fg r a p ht h e o r y t h e c o l o r i n gt h e o r yh a sm a n yk i n d s ，s u c ha se d g ec o l o r i n g ，v e r t e xc o l o r i n g ，f a c ec o l o r i n g ， t o t a lc o l o r i n ga n ds oo n a m o n gt h e m ，t h ee d g ec o l o r i n gi sg i v e nm o s ta t t e n t i o n a n dh a sm a n yp e r f e c tr e s u l t s t h ep r o p e re d g ec o l o r i n gi st od i v i d et h ee d g es e t o fgi n t os o m ed i j o i n ti n d e p e n d e n te d g es e t s i np r o p e re d g ec o l o r i n gt h e o r y , i ti s w e l lk n o w nt h a tv i z i n g st h e o r e ma n dt h ec l a s s i f i c a t i o np r o b l e m r e c e n t l y , m a u y a u t h o r sc o n s i d e rt h eg e n e r a l i z a t i o no fp r o p e re d g ec o l o r i n g ，t h a ti s ，w ec 衄c o n s i d e r o t h e rf o r m si nw h i c hw ec a nd i 、，i ( 1 et h ee d g es e t t h ea i mo f t h i st h e s i si st od i s c u s s s o m et o p i c so ne d g ec o l o r i n gp r o b l e m ss u c ha se d g ec o v e rc o l o r i n g ，- e d g ec o v e r c o l o r i n g ，f r a c t i o n a le d g ec o v e rc l o r i n ga n df i a c t i o n a le d g ec o l o r i n go fg r a p l l 8 l e tg ( v e ) b eag r a p hw i t hv e r t e xs e tva n de d g es e te i fsi sas e t ，w e s h a l ld e n o t eb yi s it h ec a r d i n a l i t yo fs t 1 l r o u g h o u tt h i st h e s i st h et e r mg r a p h i su s e dt od e n o t eas i m p l eg r a p hgw i t hf i n i t ev e r t e xs e tva n daf i n i t ee d g e s e te i fm u l t i p l ee d g e sa r ea l l o w e d gi sc a l l e dam u l t i g r a p h f o rav e r t e x 口 o fg ，t h ed e g r e eo f 口i ngi sd e n o t e db yd a ( 口) l e ty a ( v ) d e n o t et h e8 e t0 f n e i g h b o r so fv e r t e xt ，s e ta ( c ) = r a i n d g ( 钉) ：t ，y ( g ) ，t h en l i n i m u l nd e g r e e o fg ，a n dz x ( g ) = m a x d a ( 口) ：u y ( g ) ，t h em a x i m u md e g r e eo fg i ft h e r e i sn oc o n f u s i o n ，w eu s ev e ，) ，正ai n s t e a do fy ( g ) ，e ( g ) ，n a ( t ，) ，6 ( g ) ，( g ) ， r e s p e c t i v e l y l e tg 6d e n o t et h es u b g r a p ho fgi n d u c e db yt h ev e r t i c e so fd e g r e e6 gi s r e g u l a ri f ( g ) = a ( c ) = d ，w ea l s os a yt h a tgi s & r e g u l a r ag r a p hi sc u b i ci f i t i s3 - r e g u l a r ag r a p hgi sb i p a r t i t ei ft h e r ee x i s t sap a r t i t i o n ( ，) o fv ( c ) v 山东大学博士学位论文 s u c ht h a te a c he d g eo fgj o i u sav e r t e xo f t oav e r t e xo fk an e a r l yb i p a r t i t e g r a p h i sa g r a p h g w i t ha v e r t e x o f gs u c h t h a t g 一“i sa b i p a r t i t eg r a p h w i t h b i p a r t i t i o n ( x ，y ) ，d e n o t e db ya ( x ，y ；乱) ac o n n e c t e dg r a p hi se u l e r i a ni fd ( v ) i se v e nf o ra l l 口y ( g ) ac o n n e c t e dg r a p hi sc y c l ei fd ( v ) = 2f o ra l lv y ( g ) i fa c y c l eh a sa l lo d dn u m b e ro fe d g e s ，i ti sc a l l e da no d dc y c l e o t h e r w i s e i ti sa n e v e nc y c l e w ea s s o c i a t ep o s i t i v ei n t e g e r1 ，2 ，w i t hc o l o r s ，a n dw ec a l lc a k - e d g e c o l o r i n go fgi fc ：e _ 1 ，2 ，耐l e tg ( t ，) d e n o t et h en u m b e ro fe d g e so f gi n c i d e n tw i t hv e r t e x t h a tr e c e i v ec o l o rib yt h ec o l o r i n gc a s s u m et h a ta p o s i t i v ei n t e g e rf ( v ) w i t h1 ( v ) d ( v ) i sa s s o c i a t e dw i t he a c hv e r t e x 口v w ec a l lc 锄f - e d g ec o v e rc o l o r i n go fgi ff o re a c hv e r t e xu v ，g ( ) f ( v ) f o ri = 1 ，2 ，k ，t h a ti se a c hc o l o ra p p e a r sa te a c hv e r t e xu va tl e a s tf ( v ) t i m e s l e t 玩( g ) d e n o t e t h ei n d 2 g m u n 1n u m b e ro fc o l o r sf o rw h i c ha nf - e d g ec o v e r c o l o r i n go fg e x i s t s w ec a l lx k ( g ) t h ef e d g ec o v e rc h r o m a t i ci n d e xo fg l e t 母2 恕 【器i t i s k n o w n t h a t 毋一1 x 欠( g ) 出 f r o mt h ea b o v ec o n c l u s i o n ，w ec a ns e et h a tt h e ，一e d g ec o v e rc h r o m a t i ci n d e xo f a n yg r a p hg m u s tb ee q u a lt o6 fo r6 | 一1 t h i si m m e d i a t e l yg i v e su sas i m p l ew a y o fc l a s s i f y i n gg r a p h si n t ot w ot y p e sa c c o r d i n gt ox ，c ( g ) m o r ep r e c i s e l y , w es a y t h a tg i so f c ic l a s si f x ；。( g ) = 毋，a n dt h a tgi so f qi ic l a s si f 】( 欠( g ) = 毋一1 i f ( v ) = 1f o ra l l 口v ，t h e n 毋= 6a n df - e d g ec o v e rc o l o r i n gi sr e d u c e dt oe d g e c o v e rc o l o r i n g c o r r e s p o n d i n g l y , w eh a v ee d g ec o v e rc h r o m a t i ci n d e x 砭( g ) s u c h t h a tj 一1 砭( g ) 6 ，a n dt h ec l a s s i f i c a t i o np r o b l e mo ne d g ec o v e rc o l o r i n gi s t h a tgi so fc ic l a s si f 疋( g ) = 6 ，a n dt h a tgi so fc i ic l a s si f 砭( g ) = 6 1 i ng e n e r a l ，t h ep r o b l e mo fd e t e r m i n i n gt h ee d g ec o v e rc h r o m a t i ci n d e xo f 窜a p h s i sn p - c o m p l e t eb e c a u s ed e c i d i n gw h e t h e ra3 - c o n n e c t e dc u b i cg r a p hgi sp r o p e r 3 - e d g ec o l o r a b l ei sn p - c o m p l e t e ，w h i c hi st h es p e c i a lc a s eo fo u rg e n e r a lp r o b l e m b u ti t i sp o s s i b l et od e t e r m i n et h ev a l u eo f 慰( g ) o fs o m es p e c i a lg r a p l l s i n c l a s s i f i c a t i o np r o b l e m ，t h ec o n c e p t i o no f c r i t i c a l ”i sv e r yi m p o r t a n t l e tgb ea c o n n e c t e da n dn o tc o m p l e t eg r a p hw i t hz ，o ( a ) = 以一1 i ff o ra n yu ，秽va n d e = 伽簪e ，t h e r ei s 形c ( g + e ) = 0 ，t h e ng i sc a l l e da n - e d g ec o v e r e dc r i t i c a l 山东大学博士学位论文 g r a p h s i m i l a r l y , i f ( v ) = 1f o ra l l 御v ，w ea l s oh a v et h ee d g ec o v e r e dc r i t i c a l g r a p h s t h ep r o p e r t i e sa n d t h ec o n s t r u c t i o n so ff - e d g ec o v e r e dc r i t i c a lg r a p h s ( o r e d g ec o v e r e dc r i t i c a lg r a p h s ) a r ei m p o r t a n tf o rt h ec l a s s i f i c a t i o np r o b l e mo nf - e d g e c o v e rc o l o r i n g ( o re d g ec o v e rc o l o r i n g ) s i n c et h ef r a c t i o n a le d g ec o v e rc h r o m a t i ci n d e xa n dt h ef r a c t i o n a le d g ec h r o - m a t i ci n d e xi sa ni m p o r t a n tt o o lf o rs t u d y i n gc l a s s i f i c a t i o np r o b l e m ，m a n ya u t h o r s s t u d i e dt h ef r a c t i o n a le d g ec o v e rc o l o r i n ga n df r a c t i o n a le d g ec o l o r i n go f 酽印h s af r a c t i o n a le d g ec o v e rc o l o r i n gi sa na s s i g n m e n tuo fn o n n e g a t i v ew e i g h t st o t h es e to f e d g ec o v e r so fgs u c ht h a tf o re a c he e ( g ) w eh a v e c * w c 1 t h e nt h ef r a c t i o n a le d g ec o v e rc h r o m a t i ci n d e xo f g r a p hg ，x ( g ) ，i st h em a x i m m n v a l u eo f cw c ( w h e r et h es u mi so v e ra l le d g ec o v e r sca n dt h em a x i m u mi so v e r a l lf r a c t i o n a le d g ec o v e rc o l o r i n g su 1 s i m i l a r l y , af r a c t i o n a le d g ec o l o r i n gi sa na s s i g n m e n to fan o n n e g a t i v ew e i g h t - t oe a c hm a t c h i n gm o fg ，s u c ht h a tf o re a c he d g eew eh a v e m j e w m 1 t h e nt h ef r a c t i o n a le d g ec h r o m a t i ci n d e xo fg r a p hg ，珥( g ) ，i st h em i n i m u mv a l u e o f mo , m ( w h e r et h es l l l i so v e ra l lm a t c b a n gm a n dt h em i n i m u mi so v e ra l l f r a c t i o n a le d 蓉ec o l o r i n g su ) w ec a nf i n dt h a tt h er e s u l t so ne d g ec o v e rc o l o r i n g & r es i m i l a rw i t ht h o s eo f p r o p e re d g ec o l o r i n g b u tw ec a nn o td e d u c et h e mf r o me a c ho t h e r t h em e t h o d s o fr e s e a r c ha r ev e r yd i f f e r e n ta n dt h e i rr e s e a r c h sa r ei n d e p e n d e n t t h et h e s i si sd i v i d e di n t of i v ec h a p t e r s as h o r tb u tr e l a t i v e l yc o m p l e t es u r - v e ya b o u te d g ec o l o r i n gi sg i v e ni nc h a p t e r1 w ec o n s i d e rt h ec l a s s i f i c a t i o no n e d g ec o v e rc o l o r i n go fg r a p h sa n dt h ep r o p e r t i e so fe d g ec o v e r e dc r i t i c a lg r a p h s ， w ea l s og i v eam e t h o dt oc o n s t r u c tas p e c i a lc l a s so fe d g ec o v e r e dc r i t i c a lg r a p h 8 i nc h a p t e r2 i nc h a p t e r3 ，w ei n t r o d u c es o m ed e f i n i t i o n sa n dp r o g r e s so f - e d g e c o v e rc o l o r i n go fg r a p h sa n dg i v es o m es u f f i c i e n tc o n d i t i o n sf o rag r a p ht ob eo f q ic l a s s w ed i s c u s st h ec l a s s i f i c a t i o np r o b l e mo fc o m p l e t eg r a p h so nf - e d g e c o v e rc o l o r i n g s o m ep r o p e r t i e so nf - e d g ec o v e r e dc r i t i c a lg r a p ha r ed i s c u s s e d i n c h a p t e r4 ，w ed i s c u s st h ef r a c t i o n a le d g ec o v e rc o l o r i n go fg r 印1 1 8 s o m ep r o p e r t i e s o fx ! ( g ) a r es t u d i e d ，a n dw eg i v ea ne x a c tf o r m u l ao fx ( g ) f o ra n yg r a p hg i n c h a p t e r5 ，w ei n t r o d u c es o m ed e f i n i t i o n sa n dp r o g r e s so ff r a c t i o n a le d g ec o l o r i n g w eg i v es o m es u f f i c i e n tc o n d i t i o n sf o rag r a p hgt oh a v ex ，( g ) = ( g ) 山东大学博士学位论文 i nt h ef o l l o w i n g ，w ew i l ll i s to u rm a i nr e s u l t si nt h i st h e s i s c o n c l u s i o n1 l e tgb eag r a p hw i t hm i n i m u md e g r e e6 = 2 t h e ngi s o f c i ic l a s si l a n do n l u 矿gi sa no d dc y c l e c o n c l u s i o n2 。l e tgb eng r a p hu n t hm i n i m u md e g r e e6 hg 6i s8 s e to i s o l a t e dv e r t i c e s ，t h e ngi so fc ic l a s s c o n c l u s i o n3 l e tg ( x ，y ；u ) b ean r f fb i p a r t i t eg r a p hw i t hm i n i m u m d e g r e e6 3 f d ( u ) 22 6 1 ，t h e n a ( x ，y ；u ) i s 口，c ic l a s s c o n c l u s i o n4 l e ta ( x ，y ；u ) b ean e a r l yb i p a r t i t eg r a p hw i t hm i n i m md e g r e e6 3 x y n c ( u ) c o n t a i n sa tm o s to n em i n i m u md e g r e ev e r t e 易t h e na ( x ，y ；) i so l c ic l a s s c o n c l u s i o n5 l e ta ( x ，y ；u ) b ea 竹b o 嘶b i p a r t z t eg r a p hw i t hm i n i m u md e w e ej 3a n ds = t ，n g ( u ) l ：( v ) = 6 ) 巧s x ( o r y ) a n d d ( u ) 6 + i s i 一1 ， t h e n a ( x ，y ；u ) i s 盯c c a s 8 w e c a l l 口a 如v e r t e x i f d ( v ) = 毋，( 钉) c l e a r l y , i f ( v ) = 1 f o r a u t ，v ，t h e n t h e6 l v e r t e xi st h ev e r t e xw i t hm i n i m u md e g r e e6 l e t 肚毋= 【器卅，w 却：曲= 鬻，口卅 c o n c l u s i o n6 l e tgb eog r a p h l e t ( v ) a n dv b ed e f i n e da se a r l i e r 巧 ，( 矿) 十d ( 矿) ，d ra l l 矿v + t h e n gi so f o ，c l a s s c o n c l u s i o n7 l e tgb e 口g r a p h l e t ，( 秽) ，d ( ) ，毋a n dw b ed e f i n e da s e a r l i e r , l | v ii sas e t0 | i s o l a t e dv e r t i c e si ng r a p hg it h e ng i so c ilc l a s s c o n c l u s i o n8 l e tgb enc o m p l e t eg r a p hw i t ho r d e rn 玎而a n dna r eo d d i n t e g e r s , ( v ) = ka n dkld ( v ) f o ra l l 口v ，t h e ngi so f ohc l a s s o t h e r w i s e , 山东大学博士学位论文 g 话0 | c | i c l a s s c o n c l u s i o n9 l e tgb ea n 一e d g ec o v e r e dc m t i e a lg r a p h t h e ni o re a c h u ， va n de = u u e ，t h e r ee z z s t sw u ， ) 础z md ( w ) 曼巧，( 厂( ) + 1 ) 一2 s u c ht h a t 叫i so 由n c e 耐t oa tl e a s t d ( w ) 一以f ( w ) + 1v e r t i c e sw h i c ha t ea l l 毋一v e r t e x z ng c o n c l u s i o n1 0 l e tgb eag r a p h t h e n 姗刮g ) n 圳( g ) = 呼鼢， w h e r esi st h en o n e m p t ys u b s e t so fv ( c ) w i t hl s lo d d a n dc 吲s t a n d s o rt h o s e e e st h a th a v ea tl e a s to n ee m li ns i ng r a p hg c o n c l u s i o n1 1 l e tgb eag r a p h t h e nj 一1 ；“y ( g ) i 一3 ) ，a n d ( 2 ) g h a sm i n i m u md e g r e ea tm o s t1 ， t h e n 辑( g ) = a k e y w o r d s ：e d g ec o v e rc o l o r i n g ；f - e d g ec o v e rc o l o r i n g ；f r a c t i o n a le d g e c o v e rc o l o r i n g ；f r a c t i o n a le d g ec o l o r i n g ；c h r o m a t i ci n d e x ；e d g ec o v e r e dc r i t i c a l g r a p h ；c l a s s i f i c a t i o np r o b l e m 山东大学博士学位论文 符号说明 设g 是一个图，其顶点集为v ( g ) 边集为e ( g ) 并设，是定义在点集y ( g ) 上的一个正整数值函数、 集合s 的基数 不大于x 的最大整数 大于z 的最小整数 图g 的顶点集 图g 的边集 图g 的最小度 图g 的最大度 点钉的在g 中的度数 点t ，在g 中的邻点集 图g 的重数 图g 的补图 图g 的由s 导出的子图 图g 的由最小度点导出的子图 图g 的由最大度点导出的子图 图g 的边色数 图g 的边覆盖色数 x 例h m叩粥姻郇狮脚朐酽 鲫岛 瓯煅郴 山东大学博士学位论文 缘( g ) 。 x j ( g ) x a a ) 图g 的，- 边覆盖色数 圈g 的分数边覆盖色数 图g 的分数边色数 ， 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行 研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含 任何他个人或集体已经发表或撰写过的科研成果。对本论文的研究作出 重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到 本声明的法律责任由本人承担 论文作者签名：翌边缘日期 5 ；v 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅；本人授权山东大学可以将本学位论文全部或部分内容编入有 关数据库进行检索，可以采用影印，缩印或其他复制手段保存论文和汇 编本学位论文 ( 保密的论文在解密后应遵守此规定) 论文作者签名：啦师签名：邋日期 伽6 ，沙 山东大学博士学位论文 第一章绪论 图的染色理论足图论中的一个重要分支在现实生活中有很多问题比如排 序问题、工作分配问题，时间安排、无线电频率分配、卫星通讯、交通控制等同 题最终都可归结为图的染色问题图的染色理论有很多分支，有图的点染色， 边染色面染色、全染色等等本论文主要是研究了图的边染色中的各种问题 在本章中，我们给出了一个简短但相对完整的关于边染色理论的综述全 章共分为三节，在第一节给出了基本的概念和术语第二节介绍了边染色的历 史和发展第三节介绍了本文的主要结果 1 1基本概念和术语 一个图g 是指由非空点集v ( a ) 和边集f ( g ) 及忆r 构成的有序三元组 ( g ) ，e ( g ) ，犁宙) ，其中关联函数忱