（应用数学专业论文）图的邻点可区别的全染色.pdf

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论 文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 ( 注：如没有其他需要特别声明的，本栏可空)或其他教育机构的学位或 证书使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 学位论文作者签名： 势1 序 i 导师签名：孙磊 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留，使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅本人授权学校可以将学位论文的全部或部分内容编入有关数据库 进行搜索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保 密的学位论文在解密后使用本授权书) 学位论文作者签名： 刎呼 导师签名： 矾磊 签字日期：2 0 0 8 年绛月弓日 签字日期：2 0 0 8 年4 月歹弓日 山东师范大学硕士学位论文 图的邻点可区别的全染色 刘萍 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 染色问题是图论研究的经典领域，是图论研究中一个很活跃的话题染色问题 及许多图理论均源自四色问题的研究，随着染色问题在现实中被广泛应用，各类染 色问题被相继提出并加以发展，研究 图g 的一个正常岛一染色是将是种颜色分配给g 的顶点集g ) 使得两相邻 顶点的颜色不同定义色数为x ( g ) = m 饥 南f 图g 有知一染色) f 1 】类似的，图g 的一个正常七一边染色是将七种颜色分配给g 的边集e ( g ) 使得有公共端点的两 边的颜色不同，边色数x7 ( g ) = m i n 川图g 有詹一边染色) 【1 全染色的概念是对点染色和边染色的推广，是图染色的一个传统问题，由 、，i z i n g ( 1 9 6 4 ) 【3 】b ( i h z a d ( 1 9 6 5 ) 【4 5 】各自独立提出图的全染色是对图的点，边进行染 色使得相邻或相关联的元素颜色不同在全染色的基础上张忠辅提出了邻点可区别 的全染色概念并给出了相应的猜想和两个引理哆 张忠辅给出的邻点可区别的全染色定义是这样的： 设图g ( ve ) 为阶至少为2 的简单连通图，七为正整数函数，是从1 ，( g ) u e ( g ) 到c = 1 2 ，詹 ( 也记作：c = ) 的一个映射： 对于任意顶点孔y ( g ) 记c ( 仳) = ，( 孔) ) u j f ( u t ) i 仳r e ( g ) ) 虿( u ) = c c ( 秕) ： ( 1 ) 对任意边“掣，秽z ，e ( g ) ! 且“，有，( “秽) ，( t w ) ； ( 2 ) 对任意边e ( g ) 且“口有，( u ) ，( t ，) ，( “) ，( u t ，) ，( u u ) ，( t ，) ： ( 3 ) 对于任意边u t e ( g ) 且札勘，有c ( 札) c ( u ) 若满足条件( 1 ) ( 2 ) 则称。厂为图g 的一个正常膏全染色( 简记为膏丁c ) 1 山东师范大学硕士学位论文 若满足条件( 1 ) ( 2 ) ，( 3 ) 则称，为图g 的一个七一邻点可区别的全染色( 简记 为玉a y d 丁c ) 图g 的全色数为 x 丁( g ) = m i n 七图g 有七一? c ) 图g 的邻点可区别的全色数为 x 口( g ) = m i n 七l 图g 有詹一a t ? d 丁c 下面两个关于邻点可区别的全染色的引理【2 ： 对任意阶为n ( 礼= i y ( g ) 1 2 ) 的简单连通图g 邻点可区别全色数) ( 。t ( g ) 存 在，并且 ) ( 。t ( g ) ( g ) + 1 若图g ( 矿e ) 有两相邻的最大度顶点，则 x n f ( g ) 2 ( g ) + 2 张忠辅在文献f 2 】中给出了关于邻点可区别全染色的猜想： 对任意阶为 ( 竹= j y ( g ) i 2 ) 的简单连通图g 有 ( g ) ( g ) + 3 对于路，圈，完全图，完全二部图，星，扇，轮，树等特殊图类目前已得出了其具 体的邻点可区别的全色数，并且满足上述猜想关于上述特殊图的m 可西e 2 s 七i 图， 联图和乘积图的邻点可区别的全色数已有一些结果另外，p 酣e r s e 礼图，日e 让，d d d 图，丁d m a s s e n 图及w _ 的日n j 如s “m 图的邻点可区别的全染色也已得到一些结 果 确定一个给定图的邻点可区别的全色数是n p 一困难的，本文对一些特殊图及 在某些图运算下的图的邻点可区别的全染色进行了研究 2 在本文我们得到如下结论； 坐茎堕垄盔兰巫主兰垡丝塞 _ _ - _ _ _ _ _ - _ _ _ - _ _ _ - - _ _ - - - _ _ _ _ 一一 图的插入运算： 已知图g 日且有1 1 ，( g ) = i e ( 日) ：图g 插入日是指用g 的 所有顶点一一对应地剖分日的所有边，原g 中的边不变 点扩充图： 图g 的t ，( 日) 点扩充图是指将g 的某顶点t ，用图日代替，但t 的每个邻点只分别与日的一点相邻，即： t ，的每个邻点的度不变 日酊以s u ”【1 1 ：两个点不交的图g 1 g 2 的日j 以s u 竹l ：g = ( g l z l 耖1 ) 。( g 2 z 2 剪2 ) 将z 1 z 2 粘合为一点z 删掉边z l y l z 2 y 2 增加边耖1 可2 所得其中。1 可1 z 2 可2 分别是 g 1 g 2 的边 点分裂图【1 1 】：图g 的点分裂图是指将g 的每个顶点用两个独立的点代替得到 的图，记为g 列 第一类图：若g 存在相邻最大度点且x 戚( g ) = ( g ) + 2 则称g 为第一类图 第二类图：若g 存在相邻最大度点且x o t ( g ) = ( g ) + 3 则称g 为第二类图 定理2 1 1将k 。插入g 。所得图在文献i ；6 9 中记作5 t t 。此处我们仍保持原记 法，其中1 7 ( g ) = “2 幽。) ：州k 。) = u l 川2 ) ： 1 ，( s 。) = t j l 睨，? 让1 ，札2 “，) ；e ( s 。) = 研? 铆缸z ： ：j = 1 ：n ) j t 上”口1 n l t 2 ， u n 一1 ) ：则： x 口t ( & ) = ( 岛) + 2 = n + 3 ；( n 3 ) 定理2 1 2 _ 插入g 一1 中所得图记为g 其中7 ( g + 1 ) = ( 牡l u n + 1 ) y ( 么) = u 1 ，u 。， ) ，y ( g ) = 扎1 ，t 。+ l ，t ，1 ，u n 札口， e ( g ) ： 训仇，仇 件1 加u l ，伽u n l ，u f 忱陇碱+ 1i z = 1 ，n ：这里用+ 1 表示”1 ) ； 贝4 ：x 。( g ) = ( g ) + 1 = n + 3 ，( 礼24 ) 定理2 1 3 圈g ，( g ) = u 1 ，“竹) 图日，y ( 日) = 口1 ，) 将日插入 g 所得图记为g ，v ( g 7 ) = t l ，u n u 1 ，u 。 e ( g ) = t t 仇，矾蛳+ 1 ，( = 1 ，扎；用 3 1 。定要2 。，图j p 弋矿e ) 1 0 】a ，= 玑” ? ? 1 2 ，t 瓴 ：e ： 札t 协 f ? ，w ( i ： l ，2 ，死) ；珥锈+ i ，( f = 1 ，竹一1 ) ) 贝8 ： 。 x 吡c p “，= 三：；：主：三主 pr 。，理，2 。2 令q 表示p 的批( ) 扩充图，y ( p ) ：批。彬啦，现， ： 霎p 乏，扣一! 川币= ，怎咄叩m = - ，竹一) ：y ( ：i ：；等 于乱；k u p ，( 7 = l n ) 有； 地”e ( g 2 ) ，( f ：l ，n ) 则有： 。 x 耐c g 。，= 三：芝；二二三主3 ，定理2 2 4 令凰为尸t 的另一个“( 矗) 点扩充图， 对u z 兔，y ( & ) = 钞f t 呸，嵋，吒碥】； 凳警警一罅t 卢1 i 吼心吐”i 吃址1 啦咿卜化邺朋帕 ；：i “；。，? ? _ = z _ 川；啪m 撕= z ，棚z ) ：薅享瓴：主姜小 u f 钞。，( i21 ，儿) ：贝0 ： x 。( 月五) ：扎+ 4 一一 让 设 若 4 k 接 连 m ， ， n l 啦 坩 一 乞 s 以缸 = ， 幔0 对弼，对 拟 聃却 ，飞弘 图“ i | 充 扩巧 山 劁州啪&0 听竹+ 郴似呲一 僦一h m 2 风 的 一0 “ 咱l j j p = 0 为o m 卧渍幻讹则 日币 卜 乳和 m m o 曩 2和阻l， 趣脚皓 耳目， f | 文l &卜档研舶酱蕊 z “川和 一动 ： x 扎4 g 叫且k 崛 卜弛一哦取 啐日m ，工，-， 二| 站 + g 2 1 罂圳撕羝 i i 咐l 咆即机碉搛 m 充全 y 一广琦叩附蝴篡怒 圳陋肌舸 2 彬m 泓黧慧 山东师范大学硕士学位论文 定理2 3 1 记( p n 1 ) + ( 印札7 u i ) = g 则 枷( g ) ： 越g ) + 2 朋郅 i ( g ) + 1 ， n24 定理2 3 2 记( p ”t ，。) + ( 户”掣7 己：。) = g ：贝0 ； 入口( g 7 ) = ( g 7 ) + 1 = 2 佗+ 1 定理2 3 3 令日= ( 鼠豇l 1 ) ( 晶乱“) ：则：) ( 口t ( 日) = m 口z ) ( 口( 晶) x 口( 晶) ) 定理2 4 1r 是路，则刀3 时，r 是第一类图，则r m 也是第一类图 定理2 4 2r 是扇，则们4 时，e 。分裂后满足x n ( r 【如 ) = ( r 列) + 1 定理2 4 3 啊。是轮，则钾4 时，w _ 分裂后满足x 。t ( v 【如 ) = ( 乙f ，2 ) + 1 定理2 5 1 由图晶碟碟，碟我们得到新图日其中y ( 品) = h ，t 2 “n 札1 “2 一珏。) ：y ( c 2 ) = u 畦) ：v ( 碍) = 口 一嵋) ：l ，( 岛) = f 醒) ：1 7 ( 日) = v ( & ) u v 7 ( 础) u v ( ) 7 ( 岛) ：j e 7 ( 日) = e ( & ) u e ( 碟) u e ( 铝) u e ( 碟) u 科q u ；u 。，t 澍 z ? c 爱：讹钞f 岛：l f = 1 ，n j = 1 。2 3 ) ：贝0 ； 入口t ( 日7 ) = n 一4 ，( n 4 ) 定理2 5 2 令g 1 表示尸“的顶点u 用图p 2 代替所得到的图，其中p 2 的顶点 为 “7 u ”) ，札奶“”仇，( i = 1 扎) 均为g 1 的边，则 x 。f ( g 1 ) ：2 ( g 1 ) + l 幻= 3 【( g 1 ) + 2 ，竹3 定理2 5 3 设g 为简单连通图且( g ) 47 y ( g ) = 1 1 ，) ，对g 做如下操 作：若耽e ( g ) 则添加点t k 且连接u 地，牡膏如此得到的新图记做日若g 满 足邻点可区别的全染色猜想即：x 。( g ) ( g ) + 3 则日也满足：) ( o f ( 日) ( 日) + 3 关键词：邻点可区别的全染色；图的插入运算；点分裂图；点扩充图；日町6 ss 让m 分类号： 0 1 5 7 5 5 山东师范大学硕士学位论文 a d j a c e n tv e r t e x d i s t i n g u i s h i n gt b t a lc o l o r i n g so fg r a p h s p i n gl i u s h a n d o n gn o r m a lu n i v e r s i 珏j i n a n 。s h a n d o n g 。2 5 0 0 1 4 p e o p k sr 印u b l i fo 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 mi so n po fp r i m a r 、- f i e l d si nt h es t u d ) o fg r a p ht h e o r i e s t h e c o l o r i n gp r o b l e ma 1 1 ds o m e o t h e r 黟a p ht l l e o r i e sa r e “l 矗o n lt l l es t u d yo ft l l ec e l - e b r a t e df o u rc o l o rp r o b l e m i t ht h ea p p l i c a t i o no ft h ec o l o r i n gp r o b l e ms o m e s c h o l a r sp r e s e n t e da n ds t u d i e daf e wc o l o r i n gp r o b l e mw i t hd i f f e r e n tr e s t r i c t i o n ap r o p e r 七一c o l o r i n go fg r a p hgi sa na s s i g n m e n to f 七c o l o r st oe a c hv e r t i e xi ns u c haw a 、t h a ta d j a c e n tv e r t i c e sh a ed i s t i n c tc 0 1 0 r s d m n et h ec h r o m a t i c n u m b e ro fga sx ( g ) = 2 i n 七1 9 r n p | 2g n s 七一c d 2 d r i n 9 s ) 【1 ；s i m i l a r 。ap r o p e r 詹一e d g c o l o r i n go fg r a p hg i sa na s s i g n m e mo f 五c o l o r st oe a c he d g es ot h a tn o t w oa d j a c e n te d g e s1 l a v et h cs a m ec o l o r t 1 1 ee d g e - d l r o m a t i cn u m b e ri sd e n i l e da s 入7 ( g ) = ，n jr 7 足1 9 r c 巾 g n s 七一e d 9 e c d c d r i 礼夕s ) 【1 1 t h et o t l ec o l o r i n gi sag e n e r a l i z a 土i o no ft h ec o l o r i n ga n dt h ee d g ec 0 1 0 r i n g i t s at r a d i t i o n a lc o l o r i n gp r o b l e ma n dw a si n t r o d u c e db rv i z i n g ( 1 9 6 4 ) 【3 】a n di n d e p e n d e i l t l yb e h z a d ( 1 9 6 5 ) 【4 引t h et o t a lc 0 1 0 r i n gi sd e 矗n e da sa l lo fv e r t i c e sa n de d g e s o ft h eg r a p ha r ec 0 1 0 r e di ns u c haw a yt h a tn ot w 。a d j a c e n to ri n c i d e n tc l e m e n t s a r cc o l o r e dt h cs a n l e 0 nt h eb a s i so ft h et o t a lc o l o r i n g z h a n gz h o i l g f up r e s e i l t e d t h ec o n c e p to ft h ec o n c e p to ft h ea d j a c e n tv e r t e x - d i s t i n g u i s h i n gt o t a l lc o l o r i n g sa n d g a 、，et h ec o n i e c t u r ea n dt w or e s u l t s 【引 t h ed e 矗n i t i o no fa d j a c e n tv e r t e x - d i s t i n g u i s h i n gt o t 址c o l o r i n gb yz h a n g z h o n g f ui s a sf o l l o w s ：l e tg ( ve ) i sas i m p l ea n dc o n n e c t e dg r a p ho fw h i c ht h e o r d e ri sa tl e a s t2 ，蟊i sa np o s i t i v ei n t e g e ra n d 厂i st h em 印p i n g 矗o mv ( g ) u e ( g ) t oc = 1 ，2 ，忍) o r c 网。 6 山东师范大学硕士学位论文 f 。ra 1 1 、，e r t e xt 1 厂( g ) d e n 。t ec ( 仳) = 厂( u ) ) u 厂( 札t ) i 札r e ( g ) ) c ( u ) = c c ( “) ( 1 ) f b ra n ) e d g eu r ：u t l e ( g ) a n du 叫，t h e r ei s ，( 札t ) 厂( 口钍，) ( 2 ) f b ra n ) e d g cu t e ( g ) a n d 札u t h e r pi s ，( u ) 厂( r ) 厂( “) ，( u ) 厂( 札r ) 厂( u ) ( 3 ) f o ra n ye d g eu t e ( g ) a n du r ，t h e r ei sc ( “) c ( t ) i f ( 1 ) ：( 2 ) a r es a t i s f i e d ：t h e nt 厂i sc a u e da 露一t o t a lc 0 1 0 r i n go fg r a p hg ( i nb r i e f i t i sn o t e da s 膏- 丁c 1 i f ( 1 ) ( 2 ) ( 3 ) a r es a t i s 6 e d t h e n 厂i sc a l l e da 七一a d j a c e n tv e r t e x d i s t i n g u i s h i n g t o t a lc 0 1 0 r i n go fg r a p hg ( i nb r i e f i ti sn o t e da s 五一a 1 7 d 丁p ) t h et o t a lc h r o m a t i cn 1 】瑚b e ro fgi s ) ( 丁( g ) = m i n 七igh a s 七一丁c ) t h ea d j a c e n tv e r t e x - d i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e ro fgi s 入口( g ) = m i n 后lg h a s 七- 4 17 d 丁c ) t h ef o l l o w i n gr e s u l t sa b o u ta d j a c e m 、r e r t e d i s t i n g u i s h i n gt o t a lc o l o r i n ga r e r i g h t a p p a t e n t l ) ，1 2 1 f b ras i m p l ec o n i l e c t e dg r a p l lgo fo r d e r ( ”= 1 17 ( g ) 2 ) ，a d j a c e n t v e r t e d i s t i n g u i s h i n gt o t a lc h r o m a t i c 肌m b e rx 口c ( g ) e x i s t a n d x 口( g ) ( g ) + 1 i fg ( 1 ，：e ) h a st r oa d j a c e n tm a ) ( i m md e g r e ev e r t i c e s t h e n 灭口t ( g ) ( g ) + 2 t h ef o u 伽l r i n gc o n j e c t u r ei sp r o p o s e db 、rz h a n gz o n g f ui nf 2 】= f b ras i m p l ec o n n e c t e dg r a p hgo fo r d e r 扎( n = f v ( g ) j2 2 ) t h e n x 。t ( g ) 冬( g ) + 3 7 山东师范大学硕士学位论文 t h ea d j a c e n t 、r e r t e x - d i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e ro fs o m eg r a p h s s u c ha sp a t h c i r c l e c o m p l e t eg r a p h ，2 - c o n l p l e t eg r 巾h ，s t a r f a n w h e e la n d t r e eh a v l eb e e na b t a i n e d w aa l s oh a v eo b t a i n e dt h ea d j a c e mv e r t e x - d i s t i n g u i s h i n g t o t a lc h r o m a t i cn u m b e ro ft h em y c i e l s k i 黟a p h 1 i n kg r a p ht kc a r t e s i a np r o d u c t g r a p h ，p e t e r s e i lg r a p l i h e a w | o o dg r a p h7 r ) n l a s s e ng r a p l i ，t h eh a j 5 ss u mo fw _ j e t c t h e s er e s u l t sa r es a t i s 矗e d 乞h ec o i l j e c t u r e t h ep r o b l e mo fd e t e r m i n i n gt h ea d j a c e n tv e r t e x - d i s t i n g g u i s h i n gt o t a lc h r p m a t i cn u m b e ro fag r a p hi s p - h a r d i nt h i sa r t i c l ew em a i n l 、d e a l sw i t ht h ea d j a c e n tv e r t e x d i s t i n g u i s h i n gt o t a lc h r o m a t i cn u m b e rf o rs o m es p e c i a 】g r a p h sa n dt h e g r a p h su n d e rs o m eg r a p h ：so p e r a t i o n i n t h i sa r t i c a lw eg e tt h e s ef 0 1 1 0 w i n gc o n c l u s i o n s g r a p b si n s e r to p e r a t i o n ：t h e r ea r eg r a p h sg 目a n dl y ( g ) = j y ( 日) | t h ei n s e r to p e r a t i o no fgt o 日i su s i n ge v e r yv e t e xo fgd i s s e c te a c he d g eo f 日a n dt h e e d g e so fgi 啪l ( 腑b i l v v e r t e xe x p a n d i n gg r a p h ：a sgi sag r a p h r eg e tt h eu ( 日) e x p e n d i n gg r a p h o fg 协r e p l a c i n gt h ev e r t e xro fg ag r a p h 曰b u te a e ha d j a c e n tv e r t e xo f2 j u s t a d j a c tt oo n ev e r r e xo f 日jt h a ti st h ed e g r e eo f2 d o n 。tc h a n g e h n j i 6 ss 札m 【1 1 ：l e tg 1a n dg 2b ev e r t e xd 蠲o i n tg r 即h sc o n t a i n i n ge d g e s z 1 曼，l e ( g 1 ) a n d 了2 2 e ( g 2 ) t h e 日幻( ；ss m ：g = ( g 1 z 1 可1 ) + ( g 2 ? 2 2 ) o f t l l ep a i r s ( g 1 z 1 秒1 ) 龇以( g 2 r 2 芗2 ) i so b t 越n e df r o mg 1ug 2b yi i l d e n t i f 妊i 埯z la n d z 2 ：d e l e t i n gt h ee d g ez 1y 1 z 2 y 2a n da d d i n gt h ee d g e 曼，1 可2 、，e r t e xd i s s e c t i n gg r 印h 【1 l 】：a sgi sag r a p h ：t h ev e r t i ) 【d i s s e c t i n gg r a p ho fg i so b t a i n e df r o mg 协r 印l a c i n ge a c hv e r t e xb yt o wi n d e p e n d e n tv e r t i c e s ：d e n o t e d b yg 忆 8 t h ef i r s tc l a s sg r a p h ：i fgh a v ea d j a c t e n tv e r t i e so fm o s td e g r e ea n dx 口( g ) = f g ) + 2 t h e ng i saf l r s tc l a s sg r a p h t h es e c e n dc l a s sg r 印h ： i fgh a v ea d j a c t e n tv e r t 斌o fm o s td e g r e ea n d 入n f ( g ) = ( g ) + 3 t h e ng i sas e c e n dc l a s sg r a p h w ab r i e 丑) rs u m m e r i z eo u rm a i nr e s u l t sa l sf o l l o w i n g t h e o r e m2 1 1 i n s e r tk i n t og ：v ( k ) = u 1 ) 、7 ( g ) = u 1 乱n ) eg e t 铲印h 纠j o j ( n 3 ) i “sa 铲印ht h a ti 厂( s 札) = ( t 1 。九：u 1 u n ) ：e ( s ) = 掣：u j f u i l i ：j = 1 n u 让，口l + 1 u n r l l i = 1 ：扎一1 ) ：t h e n 伦h a v ex 口f ( s ) = ( 一。) 2 t h e o r e m2 1 2i n s e r t 名i n t oc k + 1 v ( _ ) = u 1 ：，f n t ，) v ( ( 五+ 1 ) = “1 ，乱n + 1 ) v 沌g e tg r a p h g i ti sag r 印ht h a t1 ( g ) = f 1 f n ：u 1 u n + 1 ) ； ( g ) = t 上，仇u u f 耽+ 1 u 札1 札】u + 1 l i = 1 n ：u n + 1 i s u 1 ) ：t h e n w eh a v e ) l ：口f ( g ) = ( g ) + 1 = 竹+ 3 ( 扎4 ) t h e o r e m2 1 3i i l s e n 爿i i l t og 1 r ( ) = ，f j 卜q 。) g 。) = m 撕。) 、g e tg r a p hg i ti sag r a p ht h a t17 ( g ) = f 1 ：“l u n ) ：e ( g 7 ) = u ，“f t f u t + 1 i i = 1 礼：ur f + 1 i s “1 ) ：u e ( 日j i f 日s a t i s 冬t h ec o n j e c t u r eo fa d j a c e m 、，e r t e x - d i s t i n g u i s h i n gt o t a lc 0 1 0 r i n gt 1 1 a tx n f ( 日1s i h ) 。3 t h e nw eh a v e 。t ( g 7 ) s ( g ) 一3 t h e o r e m2 2 1 j p 钉i sag r 印ht h a tl7 ( 尸“) = 扣，f “f 1 1 1 t n ) ：e ( p nj = “t 。 弘口似i i = 1 ，佗) u f j 玑+ 1 i i = 1 jn 1 ) ：t h c n 、阳h a v e x n t c 尸”，= 会：；：；：；： ：至三 t h e o r e m2 2 2l e tg 2b et h eu ( k - n ) e x p a n d i n gg r a p ho f 尸n 17 ( 尸n ) = t 上t ， u l 。) ：y ( ) = u 1 ：u n ) ：a n df o ru t 尸”w em a k et 正 仇 9 山东师范大学硕士学位论文 g 2 ( i = 1 一礼) ：t h e nw eh a v e 久耐c g z ，= 会：善i ；二= ；：三i ：3 t h e o r e m2 2 3l e t 日1b ea 饥( s ) e x p a n d i n gg r a p ho fp 竹y ( s ) = 。乞： 乱i ，u 乞) ：e ( s ) = u ；巧嘭k 歹= 1 n ) u 嵋f 0 1 嘛t i i i = 1 ，n 一1 ) ； l7 ( p n ) = 仉执u j u l 1 ) ：e ( ，) ”) = 川t ；1 t ，“，l i = l ，n u t o t ，抖1i i = 1 jn 一1 ) ；批l d 硒rt 上：。兔尸”w e l a k et 上知。日1 ( i - 1 m ) ：t l l c nw e h a v e 久耐( 1 ) = 扎+ 3 t h e o r e m2 2 4 l e t 凰b ea n o t h e r 札( s ) e x p a n d i n gg r 印ho fp y ( p ) = “。 ：口l ) ：e ( p n ) = ( u q 口弘 伽i i = 1 扎) u q 奶+ l i i = 1 竹一1 ) v ( 叉) = u 1 ：u 。：仳1 u ，。) ；e ( s 。) = q 奶u i k j = 1 扎 u ( u f 饥+ l ，乱。 l i i = 1 ，n 一1 ) ：a i l df o r 秽：& f t 。尸”瓢z 1 1 a k pt ；z ，：爿2 ( i = 1 讫) ；t l l e nw eh a v e 入口t ( 吼) = n + 4 t h e o r e m2 2 5l e t 日b eau ( g ) e x p a n d i n gg r a p ho f 尸”1 ，7 ( g ) = t 上1 ：u n ) ： 1 7 ( p ”) = u ，u u 1 t 1 27 。 ：( p “) = “f i u u t 秽训，( j = 1 2 jn ) ：u f 。：+ 1 ( 1 = l ：n 1 ) a n df o r 缸f g q p 扎w em a k e 珏i 口。日( i = 1 礼) ：i fgs a t i s 冬t h e ( o n j e c t u r po fa 由a c e mv r t c x d i s t i n g u i s h i n gt o t a lc 0 1 0 r i n gt h a t 入n f ( g ) ( g ) + 3 ； t l l e l lw el l a v e 灭。t ( 日) s ( 日) + 3 t h e o r e m2 3 1l e tg = ( 尸“t 上u 1 ) + ( 户n ju 7 口i ) ，t h e nw eh a v e c g ，= ：臻主 t h e o r e m2 3 2l e tg = ( p ”，u ) + ( 户n r7 口：。) ，t h e n ) ( 口t ( g ) = ( g 7 ) + 1 t h e o r e m2 3 3l e t 日= ( ，札1 秒1 ) + ( 晶t 上j 秒i ) ，t h e n ) ( d ( h ) = m n z x 。t ( 叉) ， x n ，( ) ) 1 0 山东师范大学硕士学位论文 t h e o r e m2 4 1f i st h eg r a p ho fp a t h w h e n ”3 f ki sa 矗r s tc l a s sg r a p h t h e nr 如 i saf i r s tg r a p h t o o t h e o r e m2 4 2 f 。i st l l cg t a p ho ff a n t h e na f c e rd i s s e c t i n g e s a t i s 玲t l l a t 入耐( r 【如 ) = x 。，( r ，2 ) + 1 ( ”24 ) t h e o r e m2 4 3 _ i st h eg r a p ho fw h e e l t h e na f t e rd i s s e c t i n g _ s a t i s 枣 t h a tx 口f ( 1 1 i f 如 ) = x 。f f n 如 ) + 1 ( 门之4 ) t h e o r e m2 5 1t h e r ca r eg r a p h s & 砩暖暖；、eg e tan 孵g r a p hh f r o m t h e mw i t h1 厂( 日7 ) = y ( & ) u 、厂( 锘) u y ( 暖) u 1 7 ( 暖) a n de ( 日7 ) = e ( s ) u e ( 碟) u e ( 暖) ue ( c 甓) u u 抛： t 抛k = 1 肌t ? q ：u f ? 仉s ) t h e nw eh a v e x 耐( 7 ) = 九+ 4 ( 钉之4 ) t h e o r e m2 5 2l e tg 1b et h eg r a p ht h a ts a t i s 如ub 、bo f 尸n ：t h a tn o to n l y t 上e ( g 1 ) b u ta l s ou ”奶e ( g 1 ) t h cv e r t i r e so f 最a r e 乱7a n d 秕”：t h e nw eh a 、 x 。f ( g 1 ) ： g 1 ) + l ，扎= 3 l ( g 1 ) + 2 九3 t h e o r e m2 5 3gi sa na r b i t r a r ) s i m p l eg r a p ha n d ( g ) 4 1 ，( g ) = t ，l j 。) w pg c tan e wg r 印h b 、t h ( 、f o l l o w i n go p e r a t i o n ：i ft _ ，f 7 e ( g ) t h e n ，ca d dan e wv e t e r x 札七a n da d j a c tu 哥u 1 t 上膏t 1 7 ；i fg s a t i s f 、t h ec o i l j e c t u r co fa d j a - c e n tv e r t e x - d i s t i n g u i s h i n gt o t a lc o l o r i n gt h a t 入口( g ) 冬( g ) + 3 t h e nw eh a v e x d f ( h ) ( ) + 3 i ( e yw 6 r d s ：a d j a c e n tv e r t c x d i s t i n g u i s h i n gt o t a lc h r o m a t i ( 。n u i h b e r ；g r a p h s i n s e r to p e r a t i o n ：v e r t e xe x p a n d i n gg r a p h ：v b r t e xd i s s e c t i n gg r a p h ；h a j 6 ss u m c 1 2 l s s i f i c a t i o n ：0 1 5 7 5 1 1 山东师范大学硕士学位论文 1 1基本概念 第一章引言 在对四色定理研究过程中产生了染色问题及许多不同的其他图理论，不仅极大 得推动了图论的发展，也对其他领域产生了一定的影响 一个图g 是指一个有序对g = ( g ) e ( g ) ) 其中v ( g ) 是顶点集，e ( g ) 为边集，e ( g ) 中的边为、7 ( g ) 中两不同顶点的无序对一条边的端点称为与这 条边相关联，反之一条边称为与它的端点相关联；与同一条边关联的端点称为相邻 的，若两条边有一个公共端点则称这两条边相邻；图g 的顶点个数叫做g 的阶； 若连接同一对顶点的边数大于1 ：则称这样的边为多重边；端点重合为一点的边叫 做环；没有环和多重边的图叫做简单图，若g 的顶点集可划分为两个非空独立集