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

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意。 学位论文作者签名： 丑，及彳 导师签字；孑q 磊 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名： i _ 埂坷 导师签字：厕磊 签字日期：2 0 0 年月日签字日期：2 0 0年月日 山东师范大学硕士学位论文 图的分数染色 王顺年 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 在本文中，我们用【z j 表示不大于实数z 的最大整数用旧表示集合s 中元 素的个数 除非特别指出，本文所讨论的图均为简单，有限，无向图我们用y ( g ) 和e ( g ) 分别表示图g 的顶点集和边集对于任意顶点 p ( g ) ，用如( ”) 表示顶点t 在图 g 中的度j l v ( t ，) 表示点t 的邻域，用6 ( g ) 表示图g 中顶点的最小度g f y 】表示 图g 由顶点子集i ，导出的子图虬表示n 个顶点的完全图o ( g ) 表示图g 的 独立敦，x ，( g ) 表示圈g 的分数色数本文所用术语与符号基本与文献f 1 i 中一致 随着图的染色问题在现实中被广泛应用，它逐渐成为众多学者研究的重要领域 之一e s c i l p i n n a n 和du l l i n a n 在1 2 1 中提出了分数染色的概念，它是图染色的 分数推广作者并指出，确定任意一个图的分数色敬楚p - 完全问胚 圈g 的一个分数染色足从g 的独立集集合( 到区问【o ，l 】的一个映射c 使 得对任意顶点f 都有，c 。，c ( ，) 2i 将此分数染色的值定义为，( c ( ) 图g 的分数色数 r ( g 】足它的所有分数染色值的下确界 图g 的分数色数另一个等价定义为、，( g ) = 1 i r i l ! ! 导；1 f 竺导其中 、6 ( g ) 为g 的k 层色数给图g 的每个顶点以一个6 种颜色的色集，使得相邻两 顶点的色集不炎，若所有颜色均取臼一个n 种颜色的色集，这时，我们称图g 足 n ：扯可染的。且称此染色为个“：扛染色使得围g 有一个n ：6 - 染色的最小的 n 称为图g 的扛层色敬即、 ( g j = m i l “ig 有一个n ：6 - 染色 在本文中，关于图的分数染色，我们主要得到如下定理 定义1g 足一个图，若对g 的每个真子图，有 ，( ，) 、，( g ) ，则弥g 为分 数染色临界图 定理2 1 1分数染色临界图的顶点剖不足团 山东师范大学硕士学位论文 推论2 1 j 每个分数染色临界图是2 连通的 定理2 1 3 图g ，口y ( g ) ，x g ( ) 是g 的团 g ，由g 删去所有 t 谨：z x ) ，贝4x ，( 1 掣) x ，( g ) 一1 推论2 1 4 图a e e ( g ) ，则有x ，旧一e ) x ，( 研一1 定理2 1 5 图g ，口y ( g ) ，则有x ，( g 一) ，( g ) 一1 定理2 1 6 若圈g 是x ，( g ) 一分数染色临界图，则d ( g ) 【y ，( g ) j 一2 推论2 1 7每个图g 至少有【( g ) j 1 个度不少于l x ，( g ) 一2 的顶点 定理2 1 8 若图g h 满足g 虬h n 1 ，则g v h 必不足分数染色 临界图 子集 定理2 1 9若i i r 是分数染色临界图g 的两个顶点，则( “) 不是( t ，) 的 定理2 1 1 0若g 为，l - 临界图，且x ，( g ) = 、( g ) 则v f 矿( g ) u f ( g ) 有 、，( g 一，) = x ，( g ) 一1 ， 定理2 1 1 1若g 为 临界图，当x ( g ) 一 ，( g ) l 时，则g 为分数染色 临界图 定理2 1 1 2 图g 为分数染色临界图，且、( g ) = 、，( g ) 若y ，( g ) _ 、，( g 一，) 1 v f y ( g ) u ( g ) 则g 不楚临界图 定义2 ：8 ：j ，n j 幽圳，j i g g = ( g i n i ) + ( g 2 ，? 驰) 足由g i u 函将r 1 j 2 合成 个点，删去边7 i i z 2 啦增加边l 抛所得其中7 l l 目g i ) r 2 抛( 吼) 定理2 2 1h 町幻s m l g = ( g i ，z l 封1 ) + ( g 2 ，z 2 妇) 则m “ x ，( g 1 ) ，x ，( g 2 ) 一l x ，( g ) sm “f ( g i ) ，x ，( g 2 ) 注上下界不能改进 2 山东师范大学硕士学位论文 推论2 2 2h 可如s u m g = ( g 1 ，l 们) + ( g 2 ，现抛) ，若g l ，g 2 中分数色效最大 者是非分数染色临界图，则x ，( g ) = m “f x ，( g 1 ) ，x ，( g 2 ) ) 定理2 2 3 凰巧6 ss u m g ，g = ( ， l 2 ) + ( k m ，“1 u 2 ) ， l ，“l 合成一个点若 m = n 则x ，( g ) ；n l 2 ，否则x ，( g ) z m “h ( ) ，x ( 尬n ) 一1 定理2 2 4日叮曲s “m g = ( 0 ，玑谁) + ( 以，“l “2 ) 是分数染色临界图，其中 们，n 1 合成点珊，连接p 2 ，“2 定义3 9 j 给2 + l ( 1 ) 个图g 0 ，g l ，g 2 ，g 2 k ，对i = o ，l ，2 ，2 ，令 e i = 饥扯+ l e ( g 。) 岛 + l = ，c l ，一，锄) 为长是2 + 1 的图，构造新图， ( 1 ) 删去e i i = 0 1 2 ，2 女， ( 2 ) 合并所有的n 成一个点为 ( 3 j 将2 “i 与g 合成一个点f = o 1 2 。，驰“+ 1 取模2 女+ 】) 令此图为s l ( g o p f l g i ，e i g 2 e ”一，g e 2 i ) 简记为函 定理2 2 5图s l ( g f j 印g 1 e i g 2 8 2 g m _ 1 e 。一i ) 简记为s i 若、，( g ) 2 4 则x ，( g ) 一l 、，( & ) 曼 ，( g ) 其中、，( g ) = m a x x ，( g o ) ，x ，( g 1 ) 、，( g 州一1 ) 洼t 其上下界不能改进 推论2 2 8 对上述s 图中g ，：b0 1 m l ，若分数色数最大者非分数 染色临界图，则、，( 鼠) = 1 1 1 “，( g t ) ： = o 1 ，m 1 ) 若给定l ，l 3 ) 个图g ，= 虬，f ；1 2 m 则岛( g o 伽g i e i g 2 即，g 2 ( t 2 - ) = s t i ( 。f i 儿r 2 ，j 。虬p 。) 简记为舅 定理2 - 2 7 爿为上述图，则x ，( 爿) = 、，( _ ) 一赤 令q 中给定的m 个图g 。全为奇圈g 得s i = ( c 1 c i c 2 也c n ，) 简记 为s ： 定理2 2 8 5 7 为上述图，则、，( 卅) = 3 一i 再幻 定义4 f 9 ：给n 个图g b g i g 2 ，g i _ l ，令q = 而瓠e ( g i ) = o ，1 2 ，n 1 构造新图， ( 1 ) 删去龟i = o 1 ，2 ，l l ， 3 山东师范大学硬士学位论文 ( 2 ) 将挑与。件l 合成一个点，l = o ，1 ，2 ，n 一1 ，( 下标取模n ) ( 3 ) 连接边毛与+ 2 江o ，1 ，2 ，l 一1 ， ( 4 ) 增加点“并连接点“与反j = o ，1 ，2 ，n l ， 令此图为昆( g 0 ，e o ，g l ，e l ，g 2 ，e 2 ，g 。“e 。一1 ) 简记为s 2 定理2 2 9 岛为上述图，则m “n ，( g i ) ：t = 1 ，2 ，n 一1 一1 ，( ) m a ) 【 x ，( g ) ： = 1 ，2 ，n 一1 ) + 1 注t 其下界不能改进 定义5 1 叫给4 k 个图g o ，g 1 ，g 2 ，g 4 k l ，七3 ，i 互o ，l ，4 七一1 岛= 玑 e ( g ：) ，令q k = ( c 0 c l 一，。肽一1 ) 为长为2 的圈构造新图t ( 1 ) 删去岛， = 0 1 2 ，4 k 一1 ( 2 ) 将跏z i 一z 2 i l 合成一个点z 对i = o 1 2 一，2 一l ，将”。与q 合成 一个点。 ( 3 ) 对待2 2 女+ 1 1 一1 将与q 一2 i 合成一个点。肌与q 一2 3 合成 一个点，下标模2 k 令此图s 3 ( g n c o g i r 卜g | 。2 g 仙一卜8 蚺一1 ) 简记为s 3 定理2 2 1 0 岛为上述图，若l i l “ 、，( g 。) ：f = o 1 ，2 ，4 一1 ) 7 则 l n a x x ，( g 。) ：i 之o 1 2 j 七一l 卜l x ，( s 3 ) sl l l a x 、，( g i ) ：f = o ，1 2 ，一4 七一1 ) 注；其上下界不能改进 推论2 2 1 l 对上述岛图中g ，：j = o 1 从一l ，若分数色数最大者非分 数染色临界图，则、，( 鼠) = l i l “，( g 。) ：i = o 1 。i 女一l 定义6 ：t 给定7 个图g i q g i n 为5 个点的路令q = t 。肌e ( g 。) f = 1 2 7 构造新图如下t ( 1 ) 删去边r 。f = 1 2 7 ( 2 ) 将，1 舭1 舶合成个点，记为将 与b 合成一个点，记为 i = 1 2 ，5 ( 3 ) 将j 6 与2 ! ，6 与j 川i 与。1 们与，4 分别合成一点 记此图为鼠( g 1 e 1 g 2 9 g 7 e 7 ) 简记为最 定理2 2 1 2s 4 为上述图，若l n a x 、，( g j ) ：i = l ，2 ，7 ) 6 ，则m “ 、，( gj i = 1 2 ，7 ) 一lsx ，( s 1 ) s m a x 、，( g 。) ：i = 1 2 ，7 山东师范大学硕士学位论文 注，其上下界不能改进 推论2 2 1 3对上述& 图中g ：t = 1 ，2 ，7 ，若分数色数最大者非分数染 色临界图，则x ，( ) = m “ ，( g ) ：i = l ，2 ，7 ) 定义7 距离联图g 场g ，g ，为g 的复制，y ( g ) ； l ，2 ，) ，矿( g ，) = 1 ”，n ”，d = u o ，y ( g g ，) = y ( g ) u 矿( g ，) ，耳g 场g ，) = e ( g ) u e ( g ，) u ( ，) l d ( 以，) = k ，d ，为，y ( g ) 的对应点) 引理2 3 1距离联图g 场g ，d = o ，1 ) 中任意独立集，都有g ( 或g ，) 中 的独立集，7 ( 或，”) 与之对应，使得，( f ) = ，( 州= ，砸”) ) ，其中，为 难，r ， ”，” g 和g 7 的最优分数团，为由，7 确定的分数团， 巾) ：即一f ，( g ) 【，( ”) ，y ( g ，) 定理2 3 2 g 场g d = o 1 是距离联图。则y ，( g 场g ) = 2 x ，( g ) 定理2 3 3若g 为分数染色l 临界图，则距离联圈g g d = ( o 1 为分数 染色临界图 定理2 3 4距离联图g ，i b 已上) = k 则 叫仨巍。未。 注；n ( gj = 2 一 + 1 等号成立 州印嘲隹燮蠹三：+ ， 5 l 东师范大学硬士学位论文 注：n ( g ) = mh 寸x ，( g 场暖) = 2 x ，( g ) ，n ( g ) = 2 m 一+ 1 时x ，( g 暖) = 黼 。 定理2 3 6距离联图g 场暖，d = + l ，sm 一1 则x ，( g 场诺) s 戤，( g ) 注，a ( g ) = m ，等号成立 则 定理2 3 7 距离联图c ；v ，d 碟，d = ，+ 2 ，+ ，f 为偶数，且k + l s m 州g 嘲佳纛一三。 注：o ( 研= 2 m 一( - + i ) 一l ，等9 成立 定义8 ：l l l 圈g ，伊( g ) = ， ，t ，? 及伊( g ) 整数，n21 g 的m 一 ，c i e f s 七胁n 记为，l ，。( gj 其点集为； v ou 矿1u 矿2u uy mu f ， 其中l ，= _ i ? 伊) 为y o 的第f 个复制，f = 1 2 ，玎l 边集为： ，m l、 一u ( u ，j ，1 ：? r ) u r 了l “：了2 ， i ，f 0 ( g ) 为由c 加一个控制点构成 g 的、i y = s k - 为，- ( g ) ，即为，l ( g ) c l a l i i c1 h r t 在| 1 2 l 巾给出了x ，( ，。( g ) ) = ，( + 百未 ! b 南奉文给出了 、，( ，- ，。( g ) ) i ：界的另一种证明 定理2 4 1g 为任意图，、，( g ) 一二“6 且g 有个“：b 染色，则冈m ( g ) 整 数，n i i ，、，( ，f ( g ) ) 暑i 簪其f b h 、厶m 1 厶一( ，一 ) i i 扣一 ) 川1 扣一 j ” 定理2 4 2图，k 。( k ) ，整数w 1 ”3 为分数染色l f 缶界闱 定义9 冈g 有一个控制点。g ，为g 的复制，罔( 形定义如i ? ：l ( g r c 盯j = v ( 6 ) u 矿( g ) e ( d 矿g ) = e ( g ) ue ( g 7 ) u l 。：i 矿( g 7 jn 为控制点 ，o 矿( 6 f ) u “：“为g 中控制点t ：ev ( ) 6 山东师范大学硕士学位论文 定理2 4 3 g 珊是上述图，则x ，( g 甲g ，) = 苍，( g ) + 1 关键词：分数染色；分数染色临界图；分数团；a ：b 染色；p 。( g ) 图 分类号： 0 1 5 7 5 山东师范大学硕士学位论文 n a c t i o n a lc o l o r i n g so fg r a p h s s l l i l m l j a nm m g s 1 l a l t d o l i gn o n n a lu 1 1 v e 商t y ij j i i a n ，s l l a i l d o n g ，2 5 0 0 1 4 p e o p l e sr p l l b l i co fc l i i l l a a b s t r a c t i nt h i s 盯t i c l e w en s ei z jf o rt h en l a x i m u mi n t e g e rw h i c hi sn om o r et h a n t h er e a lm l m b 盯z w el i 靶z 1f o rt h em i n i m l i mi n t e g 盯w h i c hi sn oi e s st h a nt h e r e a ln u m b e rz 、- ed e n o t eb yf 刮t h em l m b e ro f t h ee l e m 龇t si nt h es e t a i lg r a p h s ( o n s i d e i 瓴ia “：s i f i l i l l e ：“n t ea n du n d i r e c tc r i f o rag r a l ) hg w 譬 i l t n o t ct h 竹t c x 鲫ta n df l l ep ( 1 即鲫to fgb v ( g ) h n de ( g ) r 硝p c c t i w i y 、垤 n s cd o ( r ) f 1 ) r t l l c 【i 唱r 坩t j fr i l l 7 ( g ) a l 、t l ( g ) f 0 t t l l t l n l 腻i 1 1 n u nd c g t o f ga n d ( g ) f o rt l i cn l i i i i l l i l id r g r vo fg l t ，tg 【l ( i e n o t ct hi n ( 1 1 l c c d 洲b ；r a l ) ho fg w j f l l 、_ r f “蝌l j 洲dg f f + l ( i f ，l i d f r h c 胁l l i c 卅州l 镩_ a j ) l id fg 聃+ i t l | c f 培e 船tf 、i d n l ( 计pt ) 、ht l l e ( m i p l t t pg r a l ) l i mn c r t i c 惴、01 l 靶t h cs ) - t t i b o i so ( g ) a n d ( g ! ) t jd r n o t t t l i cn t l i l b t r j f ( j n - 1 ) o n e l l t so fg a n dt h ec n l n e c t i v i t yo fg t l i ci l l i p i ) c l l d n i c r1 1 1 l l l l l ) p ro fgi sd p l l o t c ( 1l 磅n ( g ) a n dt h cc h m m a t i cn l i b e ro f gbd c l l o t t ( i l 磅、( g ) n ，ra f l yl l f h m i l l c 【i i l o t a li o na i l e n l l i n o l o g y ，w er l ! f e rt h e t h c 【l c f j i l i l “j 1 1o ff r i i f j l l l l 【l f j r | i l gi sg 、c ni i l1 6 ib ye s ( h c i l l c n l l a na n d i ) 【i l l i l j ti sf r a ( f i 小h ig - n i i i z l t 汕1 ) fc o k 库i l l g j fg r a l ) l l s 0 1 ，f ；i i np d g r a l ) 1 i sf r a m m i l ( 1 l m 川州r1 1 1 l l i i l j t ri s v ，一l i a r ( 1 ：、l i t l ) 1 ) 1 l g ( jm 川it i p “川晾n ( “i l i ( ) l l t t sf j f ag r 埘) hgt o t l “i n t t n n ln j 1 】i snf 1 t i m i 一“n r j l l gi fr 盯t 、t r ，、“x ru f “w ph n 、 ，( c 。，c ，( ? ( ，) 1 t l i t 、_ l i ”f i f r 小t i l l a l 一“j l ( j r i l i g ( ? 讧，( c ，c ，f ? ( ，) t l l c ( ，t i m l l 1 1 1 ( j l l m t i t 川l i l m l 、，( r j ) j f “i si i l l f i i l i ，f i 、州i i l 辫 rr r 伸 n a l “j l l ，r i l l g j f g i a t 沁n a k c 。k 玎讯g 。，f a 帮川山f j l l a s m l 收i i i i 、d k i l l k c i i m | f j n ，( g ) = 2 现! 坦等卫 = i ”f3 氅掣 b ( g ) 诹f 1 ”扯 小l ( 1 l r ( n f i cm m l h e r 。fg a 蝌i g n st oe a d lv e t e x o f 舀“岩fo f c o i o n ； l l “i “l j 儿f 州t 坩r t i c 雌m c t i 、ed i 由o i n t 糖t so fc o l o r s ，i fa l l 8 山东师范大学磺士学位论文 c o l o r sa r ed r 删f r o map a l e t t eo f “c o l o r s ，w bs a yt h a tgi s “：扛c o l o r a b l e w b s o m e t i m e sr e f e rt o 吼l c hac o l o r i n ga sa n 口：6 c o l o r i n g t h el e a s t 口f o rw h i c hg h a so ：扛c o l o r i n gi st h e6 - f o l dc h r o m a t i cm i m b e ro f g 舶( g ) = m i n nlgh 躺 n ：批c o l o r i n g d e f i n i t i o n1gi sf r a c t i o n a lc o l 0 1 i 卜c r - t i c a lg r p a hj fx ，( h ) x ，( g ) f o r e 、e r yp r o p e rs u b g r a p hho fg t h e o r e m2 1 1 、0 r t e xc u to ff r a c t i o n a lc o l o u r - c r i t i c a lg r a p h si sn o tc l i q l l e c o r o l l a i _ y2 1 2e 、r 、行a c t i o n a lc 0 1 0 1 l 卜c r i t i c a lg r a p hi s2 c o n n e c t e 1 t h e o r e m2 1 3 s 1 i l 1 ) ( ) 蝌g 诹a 耵a p h ，i sav e r t e xo fca n dx 、0 ( r ) i s hc l i q l l co fgc 0 1 1 t a i n e ( ii l l i t l k ，i g h b o n r h o t j du fr l e tl b eo i ) t a i n e df t o n lgb y d c l c t i l l ga l lt h ec ( 1 9 c s z ：ze 、 t h l 、，( g 7 ) ，、，( g ) 一1 c o r o l l a r y2 1 4s n ”o 蝌( ji shg r a i ) 1 1 f o rh n y 卅醇co fg t h 州1 ，( g 一) 之 、，( “) 一1 t h e o r e m2 1 5 刚1 1 ) p o 钾( ；kag r a l ) h f o ra n y 、t - r t t xi o f ( ：t h e n 、，( g 一，。) 2 、，( “) 一1 t l l e o r e m2 1 6i fgha 、，( ( 净f r h c t f j n a lc o l o 卜c r i t i c a ig r a l h t l l p n ( g ) 2l 、，( g ) j 一2 c o r o l i a r y2 1 7 i j rt 、u g r a l ) l i ( ：t c nr 【a f l c h 甜h ，( g ) j 一1 、t 吓t 峨s w l i g ，s t r l 【* st l l h ，( r ? ) j 一2 t h e o r e n l2 1 8( ：1 i i s ( ：1 ) l l 州ig ，、，卅，r 卅”2lt l l t l ig v ，珏 tf r h t t i i i i 1 l ( l j l 小r c r i f i h i9 1 1 ) i i t h e o r e n l2 1 9l fn 、i i r t ，r t i c 惜o fgw h i d li sf r a c t i u l l a j ( o l o n r - c r i t i c a i g m l 】1 1 t i l 1 v ( “) kn o ts t m 蝌tu fn ( t ) 9 山东师范大学硕士学位论文 t h m m2 1 1 0i fgi s8 nn c r i t i c a lg r a p ha n dx ，( g ) = x ( g ) ，f o ra n y e l e m e n t to f y ( g ) u e ( g ) ，t h e nx ，( g t ) = x ，( g ) 一1 t l - e o r e m2 1 1 1i fg 缸a nn _ c r i t i c a lg r a p ha i l dx ( g ) 一x ，( g ) 1 t h e ng 讧f r a c t i o n a ic o i o l l r - c r i t i c a lg r a p h t h e o r e m2 1 1 2g 凼f r a c t i o n a lc o l 0 1 i r - c r i t i c a lg r 印ha n dx ( g ) = x ，( g ) i f x ，( g ) 一x ，( g f ) f s l 则称s 足g 中的最大独立集g 的最火独立 集的顶点数称为独证数，记为n ( g ) ，l7 ( “) 中的予集s 若g 【5 鼍是完全图，则称 5 ，足g 的团 “的顶点女染色。足将件颜色分 e 给l ( g ) 的一种分配方法即将7 ( g ) 分划成( 、j 、 一i ；) 在i ：中的顶点均染，在g 的顶点染色中，如果没 有两个相邻顶点染f f f l 一种颜色，即i ：述分划中l ：“= 1 2 ) 均是g 中的独立 集，则弥这种顼点t 染色足正常的卜j _ 酐简称止常的顶点女一染色为舡染色，当g 有个一染色时，称r j 足女一r 染色的定义包数、( g ) = l l l i l i 女i g 足 可染的 符、( g ) = 则际g 足女一色冈荇f ；的f e 意咫严罔，均有、( ，) 、( g ) 则称g 足临界罔 奉义所_ l l 术i 再j 符号雇奉。i 义献【l lr f t 的致奉节未介绍的其他图沧术i 7 将在必要时于以秆l j 述 1 7 山东师范大学硕士学位论文 1 2图的分数染色概念与研究概况 与图的分数染色有关的研究最早可以追溯到1 9 7 0 年对图的多重染色的研究 e s c h e i n e r m a n 和d u m a n 在1 2 l 中有关于此专题的较为详尽的论述在这本书 中作者系统的给出了对图的理论给出他们的分数推广的方法，并从图染色的分数推 广的角度提出了图的分数染色的概念，它是图染色的分数推广作者并指出t 确定 任意个图的分数色数是尸完全问题 图g 的一个分数染色足从图g 的独立集集合( 到区间【o 1 】的一个映射e ， 使得对任意顶点z 都有，c “，。，g ( ，) 芝1 我们将此分数染色的值定义为 ，e c c ( ，) 图g 的分数色数 ，( g ) 足它的所有分数染色值的下确界 围g 的分数色数另一个等价定义为、，( g ) = j ! 堡旦铲= i i 坐铲其中 n ( g ) 为g 的良屡色数给罔g 的每个顶点以一个 种颜色的包集，使彳 相邻两 顶点的色集不交，若所有颜色均取自一个n 件颜色的色集，这时，我们称圈g 是 n ：“可染的，且称此染色为一个“：拉染色使得图g 有一个n ：扛染色的最小 的“称为网g 的拉层色数即、b ( ( ；) = l i l i n “lg 有一个a ：拉染色 图的分数染色彳图的分数吲街切牛关，网g 的一个分数团为映射，：1 7 ( g j 1 1 ) 1 1 使稚 对f e 意独证集，都有。，( r ) 曼1 我们将此分数团的值定义为 ，“r ( r ) 图g 的分数团数。，( g ) 魁它的所有分数团值的上确界 由线性规划的对偶理论可以得到t 性质1 z 肿任意图r 7 自、，( g j - 。，( f ? j 图的分数包数与分数团数红线性觇划删论中年为时偶研究网的分数团足解决 冈的分数染包的自j 放斤法 关于罔的分数染色，目前人们研究的并不多已有文献方面足研究一些特殊 罔的分数色数和阻屡色数( 如，、，m s e r 罔，循环网等】及一肫嗣运篼f 的分数色数 ( 如图乘髟 等) 另一方面足研究一些已有的关二j ：网染色猜恝是否关f 困的分数染色 成立，如，j r r ，洳一r “k r 一w 5 ：r 猜怨，“f ，t ，旷r 7 ，猜想等等分数染色临界 1 8 山东师范大学硕士学位论文 性的定义在【3 】中给出，并给出了k n r s e r 图的有关结果此领域还存在大量问题 有待进步研究有兴趣的读者可参见文献【2 ，3 ，4 ，5 ，6 】，下面引用几个重要的结果 对图g 的任意子图，显然x ，( ) s 】( ，( g ) 性质2 【 对任意图g ，x ，( g ) ：粉，当g 是顶点可传递的【7 l 等式成立 图g 称为点可传递的，如果对任意“ y ( g ) ，都存在g 的个自同构7 r 使 得7 r ( u ) = ” 性质3 1 2 j对任意图g x ，( g ) sx ( g ) 山东师范大学硬士学位论文 第二章主要结果 本章我们研究了分数染色及分数染色临界图的一些基本性质和一些图的分数 染色在2 1 节中主要给出了分数染色及分数染色临界图的一些性质在2 2 节 中主要给出了 n j 缸m 及推广的 q f 曲s “m 的分数色数的上下界在2 3 节 中，给出了距离联图的定义，并给出了它们的分数色数在2 4 节中给出了g 的 m 一 ，d e f s f o n 图zp 。( g ) 的分数色数上界的另一种证明方法，并证明了p 。( k 。) 为分数染色临界图 2 1分数染色及分数染色临界图的一些基本性质 本节主要研究了分数染色及分数染色临界图的一些基本性质 定义lg 足一个图，若对( ，f 的每个真子图有 ，( ，) ，( g ) ，则称g 为 分数染色临界图 从定义易见，每个图g 都有、，( g 卜分数染色临界图，且分数染色临界图是 连通的，类似于普通点染色临界图。对分数染色l l 缶界图也有一些性质， 定理2 1 1分数染色临界图的顶点割不足团 证明：反证法没f ? 址分数染色临界图。、，( g ) = n 6 设g 有一个顶点割s ，设“一s 的各个分支有顶点集i j ；- i ；女2 令g = g 【k u s l f = 1 由于g 足分数染色i 临界图。所以存在争 ；j = 1 工：使得 i = ，( g 。) = 吐i = 1 一 ：，不妨设f ：怂 老 = 等，将等，= 1 ：通分得鲁= 尝，其中 吼= q ，= 1 眇j ，= ，m 不妨设“，存在n ：口染色f 1 ，= 1 “取 白色集 1 2 ， ，则所有以的，“q 染色一均取白色集 1 2 ，i 。囚 为s 是团，所以s 中的符个顶点在“，的n ：q 染色g 中所取色集必不相交由 此可知，对c - f 经过若干揽换必存在g ，i = 1 ，的一组n ：q 染色a ，使它 们在s 上一致这些染色合在一起形成“的一个n ：q 染色“。而譬= 鲁 ：， 与x ，( g ) = 矛盾 山东师暂大学硕士学位论文 所以分数染色临界图的顶点割不是团 推论2 1 2 每个分数染色临界图是2 连通的 证明：若 是割点，则 l 是一个平凡的团，由定理2 1 1 。分数染色临界图 必没有割点，即每个分数染色临界图是2 连通的 定理2 1 3 图g ，f v ( “) ，x ，g ( t ) 是g 的团由g 删去所有 f ? ：卫x ，贝0 x ，( g 7 ) 27 u ( g ) 一l 证明：设x ，( g ) = 2 ，且存在一个n ：6 染色，x ，( g ) = 等，且存在一个n ，：6 ， 染色，将；等通分得2 = 鲁移= 告，现由g ，的染色构造g 的染色在g 7 原有染 色基础上连接r f z x 则可调整t ? 的色集使染色正常。最多给u 点8 种新色， 即有| 4 4 8 所以告鲁一1 ，即x ，( g ) x ，( g ) 一1 推论2 1 4 图g e e ( g ) 则有y ，( g e ) x ，( g ) 一1 定理2 1 5 图g ”v f “) 则有、，( “一) 2 、，( g ) 一1 证明。设x ，( g ) = 2 ，且俘在一个n ：6 染色，x ，( g t ) = 吾且存在一个 n ，：染色 情况lt 若、，( g l ) = 、，( g 1 结论最然成立。 情况2t 若x ，( ( 7 一l ) 、，( “) 将簪通分得2 = 鲁等= 告，假没 y ，( g l ) 、，( g ) 一1 即告 ，i ，+ 口对图g 一 重新加入点d 并 给其色集为b 种新色，则得到g 的一个正常的( - l + 疗) ：b 染色，又笋 鲁， 与、，( “) = 番矛盾 所以、，( “一f ) y ，( g ) 一1 定理2 1 6 若图f ? 足、，( r j ) 分敌染色临界图，则j ( f j ) h ，( f 圳一2 证明：设、r ( f ? ) = n 存在个n ： 染色，i f 为g 的最小度点，因为“ 为、，( f ? ) 一分数染色临界图，所以圈( ? 一，的分数色数 ，( g u ) 将u 放回已正常染色的“一中若d ( u ) = 6 ( g ) 【、，( g ，) j 一2 = 【杀j 一2 吾一2 又由定理2 1 5 得古鲁一l ，所以鲁一2 告一1 即 j 8 即可取g 中除b j 种颜色之外的b 种颜色作为“的色 2 l 山东师范大学硬士学位论文 集，这样得到g 的一个 ：b 染色，与x ，( g ) = 鲁矛盾 所以d ( g ) 【肼( g ) j 一2 推论2 1 7 每个图g 至少有【x ，( g ) j 1 个度不少于l x ，( g ) j 一2 的顶点 证明：设h 是g 的一个x ，( g ) 一分数染色临界子图，由定理2 1 6 ，的每个 顶点在打中的度不少于【x ，( g ) j 一2 ，因而在g 中的度也不少于【x ，( g ) j 2 ，由 于6 ( g ) l x ，( g ) j 一2 ，所以，至少有h ，( g ) 一1 个顶点，推论得证 定理2 1 8若图g ，月满足g _ 风，n l ，则g v 必不是分数 染色临界图 证明，设x ，( g ) = 2 x ，( ) = 5 设映射9 ：y ( g ) 一【o ，l j 是g 的一个分数 团，使得州，f g l g ( 口) = x ，( g ) = ：设映射 ：v ( h ) 一【o 1 】是日的一个分数 圃，使得。“f 1 ( t ) = y ，( ，) = 5 因为g n ，k 。所以存在t v ( g ) ， 使得g ( f ) s ；p 矿( ，) 使得 ( ) 定义映射，：y ( g v ) 一【o 1 1 其中 ， 巾) - “) 延y ( g ) 【 ( f ) 一l y ( h ) 下证，足( g v ) 一z 的一个分数团事实上，( g v ，) 一z f 的独立集或为g 中的独 立集，或为中的独立集。或为 f 而，) + ，( ) = 9 扛) + ( ) 1 ，所以，是 ( 仃v ，) 一，的一个分数团，且* i 1 m 肛圳，( t ) = 、，( g ) + 、，( ，) = ，( 仃v ，) ， 则y ，( g v ，一工f ) = i i ) ( g v ，一_ r 可) 。t ， g 。肛，帅r ( t