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

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名：王隽疽每裔 导师签字：矽卜磊 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：王氖力j 签字日期：2 0 0 8 年午月2 弓日 导师签字：规、磊 签字日期：2 0 0 9 年干月弓日 山东师范大学硕士学位论文 图的全染色、邻点可区别全染色及分数染色 王颜妮 ( 山东师范大学数学科学学院，济南，山东，2 5 0 0 1 4 ) 中文摘要 染色问题是图论研究的经典领域，它源自四色定理的研究，是图论研究中一个 很活跃的课题另外染色问题在组合分析和实际生活中有着广泛的应用，因此各类 染色问题被相继提出并加以发展、应用 图g 的一个( 正常) “染色是将七种颜色分配给g 的顶点集y ( g ) ，使得相邻两 顶点的颜色不同定义色数为：x ( g ) = m i n 川图g 有七染色) 类似地，图g 的一 个( 正常) 惫边染色是将惫种颜色分配给g 的边集e ( g ) ，使得有公共端点的两边的颜 色不同边色数x 7 ( g ) = m i i - 川图g 有后边染色) 图的全染色的概念是对点染色和边染色的推广，是对图的所有元素( 顶点和边) 都进行染色，使得相邻或关联的两元素颜色不同图的全色数x r ( g ) = m i n 川图g 有 膏全染色) 全染色是图论染色的一个传统问题，由v i z i n g ( 1 9 6 4 ) 1 1 和b e h z a d ( 1 9 6 5 ) 【2 ，3 】 各自独立提出的，同时分别给出全染色猜想 邻点可区别的全染色的概念是图的一正常的全染色且任相邻顶点的色集不同， 由张忠辅【4 】在全染色的基础上提出的，并同时给出了相应的猜想和两个引理用 x 。( g ) 表示图g 的邻点可区别的全色数 超图是般图的一个重要推广，超图的染色问题也是图的染色问题的推广1 9 6 6 年b e h z a d 首次开始超图染色的研究，逐渐地将染色理论引入到超图中来超图的全 染色的概念是图的全染色概念的一个自然推广王维凡，张克民在f 5 中给出了超图 全染色的概念，分为弱全染色和强全染色两种超图日= ( ke ) 的弱( 强) 全染色是对 超图的所有元素( 顶点和超边) 都将进行染色，使得顶点是弱( 强) 染色，边是强边染 色，并且任意关联的顶点和超边的颜色不同超图的弱( 强) 全色数) ( ( 日) = m i - - 例 超图日有弱七全染色) ( x 孚( 日) = m i n 删超图日有强七全染色) ) 图的分数染色的概念是从图染色的分数推广的角度提出的e s c h e i n e 啪a n 和 d u u m a n 在【6 】中提出了分数染色的概念，并指出确定一个图的分数色数是n p 困 难的用x ，( g ) 表示图g 的分数色数 山东师范大学硕士学位论文 在本文中，我们主要得到结论如下： 首先给出了m m 可反e f s 七i 图和类m m 可c i e f s 七i 图在全染色、邻点可区别全染 色的几个相关的结论 定义2 1 1 7 】给定图g ，顶点集y o = 口? ，t ，2 ，口边集e o ，整数m 1 图g 的 m m 箩c i e z s 殷图记为p 。( g ) 定义为：顶点集矿( 胁( g ) ) = y ou y 1uy 2u u y ”u 叫) ， 其中y i = 似旧y o ) ，t = 1 ，2 ，m 为y o 的第i 个复制，边集e ( ( g ) ) = e ou ( u 哆t 矿1 i 谚哆e o ) ) u t 于。i 咿y ”) 其中p l ( g ) 为图g 的m 西e f s 七t 图 8 定理2 1 1 设g 为礼阶非空图，整数m 1 ( a ) m 为奇数时若x t ( g ) n ，则x 丁( ( g ) ) x 丁( g ) + ( g ) ；若x 丁( g ) n ，则 x 丁( 胁( g ) ) sn + ( g ) ( b ) 仇为偶数时若x 丁( g ) 札+ 1 则x t ( m ( g ) ) s 耵( g ) + n ；若x 丁( g ) n + 1 ，则 x 丁( 肛。( g ) ) sx t ( g ) + n + 1 由定理2 1 1 可推出当m 为奇数时， ( g ) 满足全染色猜想及其达到全色数 下界的一些充分条件( 推论2 1 2 推论2 1 3 ) 定理2 1 4 设g 为6 ( g ) 2 的礼阶图，整数m 1 ( a ) m 为奇数时若x 。( g ) n ，则x 。( ( g ) ) x 。( g ) + ( g ) ：若x 。( g ) u 咿u i 哆y ”) 其中若m = 1 ，则p i ( g ) = p l ( g ) 即为m 西e l 础f 图f 8 】 定理2 1 7 设g 为儿阶非空图，整数m 2 若x t ( g ) n 一( g ) 则x t ( p ( g ) ) s x r ( g ) + 2 ( g ) ：若x 丁( g ) n 一( g ) ，则x t ( 以( g ) ) sn + ( g ) 由定理2 1 7 可推出p 幺( g ) 满足全染色猜想及其达到全色数下界的一些充分条 2 山东师范大学硕士学位论文 件( 推论2 1 隹论2 1 9 ) 定理2 1 1 0 设g 为6 ( g ) 2 的礼阶图，整数m 2 若x 口t ( g ) 扎一( g ) ，则 x 。t ( p 幺( g ) ) x 。t ( g ) + 2 ( g ) ；若x 。t ( g ) 凡一( g ) ，贝0 x 。( 幺( g ) ) sn + ( g ) 由定理2 1 1 0 可推出弘幺( g ) 满足邻点可区别全染色猜想及其达到邻点可区别 全色数下界的一些充分条件( 推论2 1 1 1 推论2 1 1 2 ) 下面四个结论主要给出了推广的两类双钻图及两一般轮的日叮如s 札m 的邻点 可区别的全色数 定义2 2 1 若图g = ( k e ) ，其中y ( g ) = 口o 1 ，t ，2 。，u 1 ，u 2 ) ，e ( g ) = u o 陇卜= 1 2 ，2 礼) u u t 秒l + l l i = l ，2 ，- 2 凡一1 ) u 口2 n 到1 ) u “1 勘i i i = 1 ，2 ，n + 1 ) u “2 u i i i = 几+ 1 ，n + 2 ，2 几，1 ，n 3 ，则称图g 为推广后的第一类双钻图特别地，扎= 3 为一 般的双钻图【9 定义2 2 2 若图g = ( v e ) ，其中y ( g ) = u o 朋，u j ，u ：，口：l - 1 u 6 ) ， e ( g ) = 可。珑i i = 1 ，2 ，一，凡) u 地秒l + 1 l l = 1 ，2 ，n 一1 ) u 口1 ) u u o 巩i i = 1 ，2 ，n ) u u 6 t ，：f i = l ，2 ，n ；口i = u 1 ：u ：= ) u t ，：口：+ 1 i = 1 ，2 ，礼一1 ； i = 口1 ，口：= u 。) u “a u ：i t = 1 2 ，n t j i = ：= ) ，礼4 则称图g 为推广后的第二类双钻图特别地，礼= 4 为一般的双钻图 9 定理2 2 1 一定理2 2 2 分别给出了这推广的两类双钻图的邻点可区别全色数 定义2 2 3 【1o 】两个点不交的图g 1 和g 2 的日叮如s u mg = ( g l ，z l 箩1 ) + ( g 2 ，z 2 y 2 ) ， 是由g 1u g 2 粘合轧z 2 为一个点，删去边z 1 箩l m 2 增加边l 可2 所得，其中。1 1 e ( g 1 ) ，z 2 2 e ( g 2 ) 令v = k lvc r 竹! y ( 矿 ) = u o ，t ，1 ，t 7 。) j e ( y k ) = ；仇+ l i t = 1 ，2 ，n ：钉。+ l = 钞1 ) u 珈仇k = 1 ，2 ，n ) w k = k 1v ，y ( ) = ， i ，? 心) ，e ( w ) = ( 钉：t 1 0 l i i = 1 2 ，m ；如+ 1 = u i ) u 嵋 批= 1 ，2 ，r n ) 定理2 2 3 _ 定理2 2 4 分别给出了两轮的辐边及其轮边作日可以s u m 的邻点可 区别全色数 下面主要给出了超图中超双星的弱全染色和强全染色以及有关全色数计数的 两个相关结论 定义2 3 1 【1 1 】中心点是u 的超星是满足下列条件的一簇s ( 口) ( 1 ) e s ( t j ) 净i e f 2 ( 2 ) e ，e 7 s ( t ，) = 争ene 7 = u ) 定义2 3 2 如上面定义的两超星s ( u ) ，s ( u ) 超星s ( u ) 中心点 的度数为d ( 口) ， 3 山东师范大学硕士学位论文 与印关联的超边为历( i = 1 ，2 ，d ( t 们超星s ( u ) 中心点的度数为d ( u ) ，与札关联 的超边为e i ，层( 待2 3 ，d ( 札) ) 其中e ( 江2 ，3 ，d ( ) ) 与层0 = 2 ，3 ，d ( “) ) 互不 相交，e 。为超星s ( t ，) 与s ( u ) 仅有的一条公共超边，则由这两个超星导出的子图称 为超双星，记为s ( ，u ) 其中口，u 称为超双星的中心，n = i 易i ( 江1 ，2 ，d ( ) ) ，= l 耳1 0 = 2 ，3 ，d ( “) ) ，= m a x d ( u ) ，d ( u ) ) 定理2 3 1 设s ( ，让) 是超双星，则弱全色数x 罗( s ( t ，u ) ) = + 1 使用+ 1 种 颜色的不同的染色方式有w ( ( s ( ”。) ) ：砭宰i + 邕一爷( 铲，一1 ) 爷( r ：一1 ) 定理2 3 2 设s ( u ，“) 是超双星，则强全色数x 孚( s ( ”，u ) ) = m + 1 使用m + 1 种颜色的不同的染色方式有帆( ( s ( u ，u ) ) = 磺岔1 硝彳1n 二i 订。磁二：，其中m = m a x m l ，m 2 ， ，m 1 = m a x n k = l ，2 ，d ( 秽) ) ，m 2 = m a x 吒悼= 2 ，d ( u ) 下面几个结论是关于复合图的两类子图的分数染色的 定义3 1 1 【1 2 】对于图g 和日设y ( g ) = ( u 1 ，“2 ，u ，n ) ，y ( 日) = 口l ，t ，2 ， 。) 它们的复合图g 定义为：y ( g 吲) = y ( g ) y ( 日) = ( 姚，) 1 1 ism ，1 j 竹) ，e ( g 【日】) = ( u 。) ( “k ，铆) i u i t 正e ( g ) 或i = 七，吻铆e ( 日) 定义3 1 2 复合图g 的一类子图，记为g 】，定义为：y ( g 旧1 ) = y ( g 【刎) ， e ( g 【日】1 ) = ( m ，) ( u k ，研) b = f ，u f u k e ( g ) 或铆e ( 日) ，让t u e ( g ) 或i = 七， e ( 日) ) 易知g 吲。为g 的子图特别地，当日为完全图时，g 嘲= g 定义3 1 3 复合图g 旧的另类子图，记为g 【驯2 ，定义为：y ( g 【驯2 ) = y ( g 【刎) ， e ( g 日】2 ) = ( t ，) ( t ，忱) 1 研e ( 日) ，啦t k e ( g ) 或i = 七，铆e ( h ) ) 引理3 1 1 【6 】设g ，日为两个图，则x ，( g 刎) = x ，( g ) x ，( 日) 引理3 1 2 若g 为长为2 的路p 2 ，则p 2 【日】1 中的任意独立集j 都对应于图日 的一独立集，7 定理3 1 3 设g ，日为两个图，则足等掣) ( ，( 日) x ，( g 【刎1 ) sx ，( g ) x ，( 日) ，其中 q ( g ) 为图g 的最大独立数特别地，若图g 为点传递图，则x ，( g 【日】1 ) = x ，( g ) x ，( 日) 下面的定理3 1 4 _ 定理3 1 7 ，分别证明了当图g 为路，偶轮，扇，完全r 部图 时， x ，( g 日】1 ) = x ，( g ) x ，( 日) = x ，( g 【刎) 定理3 1 8 设g ，日为两个图，则) ( ，( g 刎2 ) = x ，( 日) 下面两个结论是关于两类推广的日幻缸s u m 构造的分数色数上下界的 定义3 2 1 【1 3 】给m ( m 3 ) 个图g o ，g l i ，g 。乩对t = o ，1 ，m 一1 ，令e ，= 仇t 7 t + 1 g ，设= c o c l c m 一1 为长是m 的圈，构造新图： 4 ( 1 ) 删去e i ，江o ，1 ，m 一1 ( 2 ) 合并所有的仇成一个点 ( 3 ) 将仇+ - 与c i 合成一个点，江o ，1 ，m 一1 0 + 1 中的加法取模m ) 令此图为s 1 ( g o e o ，g 1 e l ，g 。- 1 e 。一1 ) ，简记为s 1 若给定m ( m23 ) 个图g 。= ，江1 ，2 ，m 则s 1 ( g o ，e o ，g l ，e ”一，g 。一l ， e f n 1 ) 2研( ，e 1 ，：，e 2 ，。e 。) ，简记为研 定理3 2 1 对上述乳有 去蚤盱赤x 舻i ) m n 。，礼m ) - 赤 特别地，若m = n ，江1 ，2 j ，m 定义3 2 2 【1 3 】给n 个图g o ： 构造新图： ( 1 ) 删去e ，i = o ，1 j ，n l 贝0 x ，( s i ) = n 一高 g 1 ，g t l 1 ，叉寸i = o ，1 ，n 一1 ，令e t = z t 剪l e ( g 。) ， ( 2 ) 将玑与z 件1 合成一个点，江o ，1 ，n 一1 ( i + l 中的加法取模札) ( 3 ) 连接边翰与以+ 2 江o ，1 ，仡一1 ( i + 2 中的加法取模n ) ( 4 ) 增加点乱并连接点“与z 。一= o ，1 ，n 一1 令此图为岛( g 0 e o ，g l ，e 1 i 一，g 。- l ，e 。一1 )简记为& 定义3 2 3 对上述定义3 2 2 ，只将条件( 3 ) 改为 ( 3 ) 连接边z i 与z ， = o ，l ，n 一1 ( i + 3 中的加法取模竹) 令此图为$ ( g o e o ，g 1 湖，g 。- l e 。一1 ) ，简记为s 5 定理3 2 2 岛为上述图，有m o z x ，( g 。) 悼 i = o ，1 ，n 一1 ) 1 = o ，l ，一，n 一1 卜1sx ，( 咒) m x ，( g 。) 关键词： 全染色，邻点可区别全染色，分数染色，( 类) m m 彬e z s 肮图，双 钻图，日幻面5 u m ，超双星，复合图 分类号： 0 1 5 7 5 5 t h et o t a lc o l o r i n g ，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 t o t a lc o l o r i n ga n dt h e 矗。a c t i o n a lc o l o r i n go f g r a p h s y a l l n iw a n g s h a n d o n gn o r m a lu n i 、他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 。i r a c t 。i h ec o l o r i n gp r o b l e mi so n eo fp r i m a r y 丘e l d s i nt h es t u d yo fg r a p ht h e o r i e s i t i sf o mt h et h es t u d yo ft h ec e l e b r a t e d f o u rc o l o rp r o b l e m i nt h ec o m b i n a t o r i “ m a t h e m a t i c sa n do u rl i 、厂i n g ，t h e c o l o r i n gp r o b l e mh a sab 培a p p l i c a t i o n ，s ow i t h t h ed e v e l o p m e n to ft h e 矗e l ds o m es c h o l a 鹪p r e s e n t e da n d s t u d i e daf e wc o l o r i n g p r o b l e mw i t hd i f l e r e i l tr e s t r i c t i o n a ( p 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 fo n eo f 七c o l o r st oe a c h v e r t e xi ns u c haw a yt h a ta d j a u 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 缸et h e c h r o m a t i c n u m b e ro fga sx ( g ) = m i n 七f g r a p hg h a s 七- e o i o r i n g s s i m i l a r ，a ( p r o p e r ) 后e d g e - c 0 1 0 r i n go fg r a p hgi sa na s s i g n m e n to fo n eo f 庇c o l o r st oe a c he d g e8 0t h a tn o t w oa d j a c e n te d g e sh 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 ri sd e f i n e da s x 7 ( g ) = m i n 忌l g r 印hgh a s 七一e d g e c o l o r i n g s t h et o t 甜c o l o r i n gi sag e n e r a l i z a t i o no ft h ec 0 1 0 r i n ga n d t h ee d g ec o l o r i n g ，a u o tt h ee l e m e n t s ( v e r t i c e sa n de d g e s ) o ft h eg r 印ha r ee o l o r e di ns u c h a 氇t h a t n ot w oa d j a c e n to ri n c i d e n te l e m e n t sa r ec 0 1 0 r e dt h es 锄e t h et o t a lc h r o m a t i c n u m b e ri sd e 矗n e da s ) ( ? ( g ) = 1 1 1 i n 七j g r a p hg h a s 七t o t a lc o l o r i n g s i t ，sat r a d i - o i o n a lc 0 1 0 r i n gp r o b l e ma n dw a si n d e p e n d e n t i yi n t r o d u c e db yv i z i n g ( 1 9 6 4 ) 1 a n d b e h z a d ( 1 9 6 5 ) f 2 ，3 丽t ht o t a lc o l o r i n gc o n j e c t u 圯 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 o i o r i n gi s at o t a lc 0 1 0 r i n ga n da 卿 a d j a u e e n tv e r t i c e sh a ed i s t i n c tc 0 1 0 rs e t i t sp r e s e n t e db yz h o n g f uz h a n g 4 】o n t h eb a u s i so ft h et o t a lc o l o r i n g ，谢t ht h ec o n j e c t u r ea i l dt w ok m m a s t h ea d j a u c e n t v 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 r0 fgi sd e n o t e db yx n f ( g ) 6 h y p e r g r 印hi sa ni m p o r t a n tg e n e r a l i z a t i o no fg r a p h t h ec 0 1 0 r i n gp r o b l e mo f h y p e r g r a p hi sa l s oag e n e r a l i z a t i o no ft h ec 0 1 0 r i n gp r o b l e m b e h z a df i r s ts t u d i e dt h e c o l o r i n gp r o b l e mo fh y p e r g r 印hi n1 9 6 6 ，t h ec o l o r i n gt h e o r i e sl e di n t ot h eh y p e 卜 g r 印hi ng r a d u a l l v t h et o t a lc 0 1 0 r i n go f h y p e r 铲印hi st h en a t u r a lg e n e r a l i z a t i o n o ft h et o t a lc 0 1 0 r i n g i tw a si n t r o d u c e db yw e i f a nw a n ga n d k e i i l e nz 1 1 a i l gi n 陬i t c o n t 出n 陀a kt o t a lc 0 1 0 r i n ga n ds t r o n gt o t a lc 0 1 0 r i n g a 伦a k ( s t r o n g ，r e s p ) t o t 酊 c o l o r i n go fh y p e r g r a p h 日= ( ve ) i st h a ta l lo ft h ee l e m e n t s ( v e t i c e s h y p e r e d g e s ) o fh y p e r g r a p ha r ec o l o r e di ns u c haw a yt h a tv e r t i c e sa r e ，e a k ( s t r o n g ，r e s p ) c o l o r - i n g ，e d g e sa r es t r o n ge d g e - c o l o r i n g d e 丘n ew e a k ( s t r o n g ，r e s p ) t o t a lc h r o m a t i cn u m - b e ro fha sx ( ) = m i n 后i h ) p e r g r a p h 日h a sw e a k “t o t a l c o l o r i n g s ) ( x 芋( 日) ： m i n 七i h y p e r g r a p h 何h a ss t r o n g 珏t o t a l - c o l o r i n g s ) ，r e s p ) t h ed e f l n i t i o no ff r a c t i o n a lc o l o r i n go f 鲈a p hi s 矗a c t i o n a lg e n e r a l i z a t i o n t h ec o l o r i n g i tw a sg i v e nb ye s c h e i n e r m a na n dd u l l m a ni n 6 】，w i t hd e t e r m i n i n g t h ef r a c t i o n a lc h r o m a t i c 肌m b e ro fag r a p hi sn p - h a r d t h ef r a c t i o n a lc h r o m a t i c n u n l b e ro fgi sd e n o t e db y ) ( ，( g ) v b r i e f l ys u m m e r i z eo u rm a i nr e s u l t sa u sf 0 i l o w ： 1 v 娓f i r s t l yo b t a i ns e v e r a lr e s u l t sa b o u tt h et o t a lc o l o r i n ga n dt h ea d j a c e n t v e r t e x - d i s t i n g u i s ht o t a lc o l o r i n go fm m 鲥e f s 兢g r 印h sa n ds i i i l i l a rm m 剪邑e f s 七z g r a p h s d e f i n i t i o n2 1 1 【7 】 g i v e nag r a p hg 谢t hv e r t e xs e ty o = f ? ，f 2 ，2 ：) ，e d - g es e t 伊，百v e na ni n t e g e rm 1 t h em m 暑，c 矧5 七施扎0 fg ，d e n o t e db y 卢m ( g ) ，w i t h v e r t e xs e ty ( 肛m ( g ) ) = y ouy 1uy 2u u y “u u ) ，w h e r ey = ；i 口? y o ) i s i 一厅d i s t i n c tc o p yo fy of o ri = 1 ，2 ，m ，e d g es e te ( p 。( g ) ) = e ou ( 旦 嵋哆产1 i 哆哆e o ) ) u 【哼u i 咿y ) w h e r ep l ( g ) i sm y 反e f s 舰。佗 8 】o fg t h e o r e m2 1 1 s u p p o s eg i san o n e m p e r t yg r 印h 谢t hn v e r t i c e s ，g i v e na n i 1 1 t e g e rm 1 ( a ) w h e nm i so d d i fx 丁( g ) 2n ，t h e nx 丁( 肛m ( g ) ) sx 丁( g ) + ( g ) ：i f ) ( r ( g ) n ：t h e nx t ( p m ( g ) ) n + ( g ) ( b ) w h e nm i se v e n i fx 丁( g ) 钆+ 1 ，t h e nx 丁( 肛m ( g ) ) x 丁( g ) + 佗；i f 7 x 丁( g ) 礼+ 1 ，t h e nx 丁( p m ( g ) ) x 丁( g ) + n + 1 b yt h e o r e m2 1 1 ，w ec a nd e d u c ts o m e s u m c i e n tc o n d i t i o n st h a tp m ( g ) s a t 讳 f i e st h et o t a lc 0 1 0 r i n gc o n j e c t u r ea n dr e a c h e st h el o w e rb o u n do ft h et o t a lc h r o m a t i c n u m b e rw h e nmi so d d ( c o r o u a r y2 1 2 一c o r o u a r y2 1 3 ) t h e o r e m2 1 4s u p p o s eg i sag r a p hw i t hnv e r t i c e sa n d6 ( g ) 22 ，g i v e n a ni n t e g e rm 1 ( a ) 、h e n 仇i so d d i fx n t ( g ) 礼，t h e nx n ( p m ( g ) ) x 耐( g ) + ( g ) ；i f ) ( 越( g ) n ，t h e nx 。( p 。( g ) ) 礼+ ( g ) ( b ) w h e nm i se 、，e n i fx q f ( g ) n + 1 ：t h e n x 越( g ) n + 1 ，t h e nx 口( p m ( g ) ) 冬x 口( g ) + 几+ 1 x a ( p m ( g ) ) x 口( g ) + n ；i f b vt h e o r e m2 1 4 w ec a nd e d u c ts o m es u 伍c i e n tc o n d i t i o n st h a t u m ( g ) s a t i s 丘e st h ea d j a c e n tv e r t e d i s t i n g u i s h i n gt o t 2 l 1c o l o r i n gc o n j e c t u r ea i l dr e a c h e st h e l o w e r b o u n do ft h ea d i 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 c 肌m b e rw h e nm i so d d ( c o r o l l a r y2 1 5 一c o r o l l a r y2 1 6 ) d e f i n i t i o n2 1 2 g i v e nag r 印hg ，丽t hv e r t e xs e ty o = 秽 u 2 ：，醒) ，e d g e s e te o ，g i v e na ni n t e g e rm21 w h e r e 仇一1c o p y 铲a p h so fg ，d e n o t e db yp f o r i ：1 ，2 ，m 一1 ，a n d 蓼a p hg w i t hv e r t e xs e t = 吗i 哆v o ) ，e d g es e t e = ( u ；，i 哆 多e o ) a n o t h e rc o p yo fy o ，d e n o t e db yy m = 哆l f ? y o 匕s i m - i l a rm 一 ，可c i e f s 舰n 竹o fg ，d e n o t e db yp 幺( g ) w i t hv e r t e xs e ty ( 肛篇( g ) ) = uy 。u l = u n h 一1 m 一2 ( u ) ，e d g es e te ( p ：n ( g ) ) = ue u u 嵋u 尹1 i u ? 哆伊) u 哆u i 哆y m ) w h e r ei f7 n = 1 ，t h e np j ( g ) = p 1 ( g ) i sm y c i e f s 尼i a 礼 8 t h e o r e m2 1 7 s u p p o s egi san o i l e m p e r t yg r 印hw i t hnv e r t i c e s ，g i v e n a ni n t e g e rm 2 i fx r ( g ) n 一( g ) ，t h e nx 丁( 肛幺( g ) ) x t ( g ) + 2 ( g ) ；i f x t ( g ) n 一( g ) ，t h e nx 丁( p 幺( g ) ) 扎+ ( g ) b vt h e o r e m2 1 7 ，w ec a nd e d u c ts o m es u m c i e n tc o n d i t i o n st h a tp ，m ( g ) s a t 诲 矗e st h et o t a l lc o l o r i n gc o n j e c t u r ea n dr e a c h e st h el a w e r b o u n do ft h et o t a lc h r o m a t i c n u m b e r ( c o r o l l a r y2 1 8 一c o r o l l a r y2 1 9 ) t h e o r e m2 1 1 0s u p p o s egi sag r a p hw i t hnv e r t i c e sa i l d6 ( g ) 之2 ，西v e n a ni n t e g e r 仇之2 i fx 口t ( g ) n 一( g ) ，t h e nx n ( p 幺( g ) ) x 口( g ) + 2 ( g ) ；i f 8 山东师范大学硕士学位论文 x 口t ( g ) n 一( g ) ，t h e nx n t ( 肛幺( g ) ) n + ( g ) b yt h e o r e m2 1 1 0 ，r ec a nd e d u c ts o m es u 伍c i e n tc o n d i t i o n st h a t 肛幺( g ) s a t i s a e st h ea d j a c e n tv e r t e x - d i s t i n 目1 i s h i n gt o t a lc o l o r i n gc o l l j e c t u r ea n dr e a c h e st h e l 旧rb o u n do ft h ea d j a c e n tv e r t e d i s t i n g u i s l l i n gt o t a lc h r o m a t i cn u m b e r ( c o r o l l a r y 2 1 1 1 一c o r o l l a u r y2 1 1 2 ) t h ef o l l 以n gf o u rr e s u l t so b t a i nt h ea 枷a c e n tv e r t e x - d i s t i n g u i s ht o t a lc h r o - m a t kn u m b e ro ft w ok i n d so fd o u b l ed i a m o n dg r 印ha 肛d 日町幽s u mo fw h e e l s d e f i n i t i o n2 2 1i fag r 印hg = ( v e ) 研t hv e r t e xs e ty ( g ) = 可o ，u 1 ， u 2 。，u 1 ：t 正2 ) ，e d g es e te ( g ) = u o 饥| i = 1 ，2 ，2 几) u _ 耽u 件1 i z = 1 ，2 ，2 n 一1 ) u u 2 n u l ) u 乱1 u t l i = l ，2 ，礼+ 1 ) u 札2 仇l i = 礼+ 1 ，扎+ 2 ，2 n ，1 ) ，f o r 礼3 ，t h e n g r 印hg i st h eg e n e r a l i z a t i o no ft h ef i r s tt y p ed o u b l ed i a m o n dg r 印h e s p e c i a l l y i f 佗= 3 ：t h e ngi st h e 丘r s tt y p ed o u b l e 出a m o n dg r a p h 9 】 d e f i n i t i o n2 2 2i fag r a p hg = ( v e ) w i t hv e r t e xs e ty ( g ) = 可o ，u 1 ， ，u ：，口：_ 1 ，t 上o 乱j ) ，e d g es e te ( g ) = 可。仇k = 1 ，2 ，n ) u “地+ 1 i i = 1 ，2 ，佗一1 ) u t ，。1 ，1 ) u 札o t ，f i i = 1 2 ，咒】u t ，；i i = 1 2 ，礼；t ，i = t j l ，1 幺= u n ) u ( 可：口：+ l i i = 1 ，2 ，n 一1 ；u i = u 1 ，u ：= ) u “：f ：l i = 1 ，2 ，n ；u i = u 1 ，u ：= 凡 ，f o rn 4 t h e ng r a p hg i st h eg e n e r a l i z a t i o no ft h es e c o n dt y p e d o u b l ed i a m o n dg r a p h e s p e c i a l l y ，i f 礼= 4 ，t h e ngi s t h es e c o n dt y p ed o u b l e d i a m o n dg r a p h 9 t h ef o l l o w i n gt h e o r e m2 2 1 一t h e o r e m2 2 2r e s p e c t i 、他l yo b t a i nt h ea d - j a c e n tv e r t e x - d i s t i n g u i s ht o t a lc h r o m a t i cn u m b e ro fg e n e r a l i z a t i o no ft w ot y p e s d o u b l ed i a m o i l d d e f i n i t i o n2 2 3 【1 0 】l e tg 1a n dg 2b ev e r t e xd 砑o i n tg r a p h s ，t h eh 幻西s u m g = ( g 1 ，z 1 箩1 ) + ( g 2 ：z 2 秒2 ) i s