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

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。据我所知，除了文中特别加阻标注和致谢的地方外，论 文中不包含其他人已经发表或撰写的研究成果，也不包含为获得一 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或 证书使用过的材料。与我同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 学位论文作者签名 加抬确 导师签名 学位论文版权使用授权书 砑撬 本学位论文作者完全了解兰筮有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅 和借阅。本人授权学校可以将学位论文的全部或部分内容编入有关数据库 进行搜索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。( 保密的学位论文在解密后使用本授权书) 学位论文作者签名：幻辛匕确导师签名：烈、磊 签字目期：2 0 0 6 年牛月t 0 日签字目期：2 0 0 6 年牟月f 口日 山东师范大学硕士学位论文 图的全染色、( 邻) 点可区别全染色及分数染色 孙艳丽 ( 山东师范大学数学科学学院，济南，山东，2 8 0 0 1 4 ) 中文摘要 染色问题及许多图理论都是源自四色问题的研究另外染色问题在组 合分析和实际生活中有着广泛的应用，是图论研究中一个很活跃的课题， 各类染色问题被相继提出并加以发展、应用 图g 的个f 正常) 七染色是将种染色分配给g 的顶点集v ( g ) ，使 得相邻两顶点的颜色不同定义色数为：x ( g ) = m i n k l 图g 有k 一染色) 类似的，图g 的一个( 正常) m 一边染色是将k 种染色分配给g 的边集e ( g ) ： 使得有公共端点的两边的颜色不同边色数x ( g ) = m i n k 图g 有k 一边 染色 全染色的概念是对点染色和边染色的推广，图的所有元素( 顶点和边) 都将染色且任相邻或关联的元素染色不同全染色是图论染色的一个传统 问题：由v i z i n g ( 1 9 6 4 ) 2 3 1 和b e h z a d ( 1 9 6 5 ) 2 4 ，2 5 各自独立提出的，同时分 别给出全染色猜想点可区别全染色和邻点可区别全染色f 2 1 是染色问题 的新生点，近来由张忠辅提出并给出了相应的两个猜想 定义设g ( ve ) 为图，k 为正整数，s 为一色集，令映射f ：v ( c ) u e ( c ) s 如果 ( 1 ) 对任意“口，v w e ( g ) ，u w ，有，( u u ) ，( ) ( 2 ) 对任意u ”e ( g ) ，有i 厂( u ) _ 厂( u ) ，( u ) ，( 删) ，( “口) ，( ”) 那么称，为图g 的一个k 一全染色若还满足 ( 3 ) 对任意“，u v ( g ) ，g ( “) g ( 口) ，其中c ( u ) = ，( u ) ) u ，( 伽) 伽 e ( g ) ) 那么称，为图g 的一个点可区别的一全染色( 简记为k - v d 7 1 c ) 若条件( 3 ) 改为 山东师范大学硕士学位论文 ( 3 ) 对任意 t i e d e ( g ) ，c t ) c t 扣) 那么称，为图g 的一个邻点可区别的一全染色( 简记为k - a v d t c ) 图g 的全色数) ( t ( g ) ( 或记为) ( ”( g ) ) = m i n k l 图g 有k 一全染色) 图 g 的点可区别的全色数x “( g ) = m i n k f 图g 自k - 矿d 了_ c ) ：图g 的邻点 可区别的全色数) ( 。( g ) = m i n k l 图g 有k - a v d t c 全染色猜想对任意简单图g ，x r ( a ) z x ( a ) + 2 邻点可区别的全染色猜想 2 】对简单图g ，) ( 。( g ) a ( a ) + 3 点可区别的全染色猜想对简单图g ，k r ( g ) sx “( g ) 墨k t ( g ) + 1 ；其 中k t ( g ) = m i n i 凹上1 n d ，6 d ，礼d 是度为d 的顶点数) 确定一给定图的全色数是n p 一困难的，目前己对许多图类( 如：完全 图、二部图、完全r 部图、部分正则图、平面同等1 和满足一定条件的图 得到了一些结论f 邻) 点可区别全染色目前只有关于特殊图的结果，例如 完全图、完全二部图、星、扇、轮及它们的联图；另外邻点可区别全染色 问题对树和上述特殊图的m y c i e l s k i 图、乘积图有一些结论 图的分数染色的概念是从图染色的分数推广的角度提出的较为详尽 的论述可见文献1 0 1 目前关于图的分数染色的研究并不多，一方面研究 特殊图的分数色数和m 一层色数；另一方面主要是考虑一些染色的猜想是 否在分数染色的意义下成立全染色猜想己被证明在此意义下是成立的 【1 1 - 本文一部分主要探讨了m y c i e l s k i 构造图和c a r t e s i a n 乘积图在全染 色、点可区别全染色及邻点可区别全染色方面与原基础图的关系从而也 得到了它们满足全染色猜想和邻点可区别全染色猜想的一些充分条件；另 外还得到特殊图类( 如：磁1 ，g 脒，雠+ 1 ( k = 0 ，l ，一，n l ，n 之3 ) ，g ，。； 、。) 在此染色方面的一些结果另一部分首先考虑了k n e s e r 图和g 。6 图 的m - 层色数，k n e s e r 图只解决了部分m - 层色数，瓯。图的m 一层色数本 文中已完全确定；其次讨论了c a r t e s i a n 乘积图的分数染色，目前只解决了 部分图乘积的分数色数：最后通过分数全染色和分数全团的对偶关系和分 数全染色的概念探讨了几类特殊图( 如：圈，完全图，完全二部图，平衡完 2 山东师范大学硕士学位论文 全r 一部图) 的分数全色数 在本文中，我们主要得到结论如下 我们称由m y c i e l s k i 作图法 2 1 得到图为m y c i e l s k i 图给定图g ，顶 点集v = 1 ，v 2 ，一，) ：图g 的m y c i e l s k i 图( 记为m ( g ) ) 定义为：顶点 集v ( m ( g ) ) = vu ( u i ，u ；，u ：，u ，边集f ( m ( g ) ) = e ( g ) u v i v l v i v j e ( g ) ，i ，j = 1 ，n ) l j 圳江1 ，n ) 定理2 1 1 设g 为n 阶图x t ( g ) n 时，x 丁( 肘( g ) ) 舸( g ) + ( g ) ；x t ( g ) 1 ) 若( g ) + 2 兰 x 砒( g ) ( g ) + 惫且x ( 日) 曼( g ) + 惫，则x 缸( g h ) ( g 日) + 七十1 一 推论2 2 5 设g ，h 为两个图，女为f 整数( 1 ) 若x n ( g ) 兰( g ) 2 且x ( 日) x “( g ) ，则g h 满足邻点可区别全染色猜想 设r ：u l u 2 札。和r = t 1 u 2 u 。为两条路在两路间逐次叠加 匹配i u l ，札1 口2 + 1 ，u 1 t 斗k ，- 】l t ij f i ( n 1 ) ( i = 1 ；2 ，n ，危二= 0 ，1 ) 凡一l ， 当z + 佗+ 1 时，i + k 为m , o dn 意义下的加法) ，这样可得到一系列图： 群，礁，磋劈“，喇= r v r 设m ： 嘶，u ，。 ，班= ( 1 ，v 2 ，一， 为两顶点集，i t l l l 2 。札n “l 和们也u 】为两个圈类似的：在两部( h ，) 间逐次叠加上述匹配：可 以得到一系列正则二部图，记为：g 端，g 瓣，g 譬：”，g = 戤”在 两圈间逐次叠加同样的匹配，可得到一系列正则图：嚷j ，g 韶，一，c 精“， 晓鼍= gvg ：且( c 黠1 ) = k + 3 定理2 3 1x 。t ( 磁甘1 ) = ( 群譬1 ) + 2 = a + 5 ( = 0 ，1 定理2 3 2 x 甜( g | ：嘉1 ) = ( g 轻去1 ) + 2 = 凫+ 3 ( k = o ，l ：一，礼一l ，n 3 ) 推论2 3 3 ( 群譬1 ) ( 群譬1 ) + 2 ，x t ( g 黠1 ) sz x ( a 譬2 1 ) + 2 ，即 砭譬”，g 瓣1 满足全染色猜想- 定理2 3 4 ) ( t ( c 黠1 ) ( g 黠1 ) + 2 = + 5 ( = 0 ，1 ，一，n i ，礼3 ) 4 山东师范大学硕士学位论文 定理2 3 5 ) ( “( g 。) = 5 ( n 3 ) 定船s 坝“吲= 掣：4 推论2 3 7w 2 。满足全染色猜想，而且当n 5 时x t ( w 缸) = ( w 矗) + 定理2 3 8 若g 为边连通度a ( a ) = 1 的图，设? 2 0 v o 为其任意割边 g l ，g 2 为图g u o 咖的连通分支且u o v ( g 1 ) ，咖v ( v 2 ) 那么。 x 耐( g ) 下面的部分将涉及到两类重要图：k n e s e r 图和g 舶图设n 2 b ，a ，b 为正整数k n e s e r 图风6 定义如下：顶点为取定的日元集的所有6 _ 子集： 若两顶点为不交集合，则两顶点相邻g 。6 图为一类循环图f 2 9 1 顶点集为 o ，1 ，。1 ) ，顶点i ，j 相邻当且仅当6 f i j f 茎n b k n e s e r 图和 g 。，b 图分别在分数染色和圆染色中起着重要的作用，它们在其中所扮演的 角色就如同完全图在顶点染色中的角色 s t a h l 1 7 】提出猜想：对任意正整数m ，x m ( 甄：6 ) = a 一2 b + 2 m 均成 立 1 4 已证明当1 m b 时猜想是成立的，下面的定理将晓明m b 时 猜想是不成立的 定理3 1 1 当o 2 b ，仃l b 时，x 。( 耽：6 ) o 一2 b + 2 m 定理3 1 2 x 砌( 玩b ) = m 。( 口，b ，m 为正整数) 定理3 1 4 设n ，b ，m 为正整数，) ( m ( g 。，6 ) = x ( g 。 ) = 警 引理3 2 1 设g ，h 为两个图，则) ( ( g h ) = m a x x ( g ) ，x ( 日) 0 g “刁皿队郇否 ，= 郇训舢 = n 让 ) l u 妣舱慨 二 曲= k m 岫 d 吣 若 g + 地 g ” m 山东师范大学硕士学位论文 定理3 2 2设g ，日为两个图，若) ( ，( g ) = x ( g ) 且x ( h ) x ( g ) ，则 x e ( a 日) = x ，( g ) 定理3 2 3 若g 含h a m i l t o n 圈，日为二- g g n ，则x s ( o h ) = x i g ) 定理3 2 4 设。：b 为正整数且。2 b ，若x ( h ) sl ：j ，则) ( ，( g 。，bx 日) = x s ( o 蛐) = ： 引理3 3 1 设g 为一个图，若) ( ”( g ) = z x ( a ) + 1 则；( g ) = ) ( ”( g ) = f g ) + 1 ) ( ；( g ) = 3 + n = 3 k + 1 l3n = 3 七 【3 + i 丽1 n = 3 k + 2 定理3 34 【12 】对完全二部图k m 。 ) ( ；( ，。) = ) ( ”( ，。) 礼是奇数 礼是偶数 髀砚耐+ 1 篓 x ；c c r 、n ，= x 弋耳c n n ，= 兰；：三；二i 萎暑r = 钆2 为或奇r 数n 偶 6 凡 礼 = 觚 全完 = 对 至= 。 理定 山东师范大学硕士学位论文 关键词：全染色；( 邻) 点可区别全染色；分数染色；m y c i e l s k i 图；乘积 图；k n e s e r 图ig 。，b 图；m 一层染色；分数全色数 分类号：0 1 5 75 7 山东师范大学硕士学位论文 t h et o t a lc o l o r i n g ，t h e ( a d j a c e n t ) v 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 ef r a c t i o n a lc o l o r i n go fg r a p h s y a n l is u n 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 ma n ds o m eo t h e rg r a p ht h e o r i e s & r ea l lf r o mt h e s t u d yo ft h ec e l e b r a t e di b 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 a lm a t h e m a t i c sa n do u rl i v i n g ，t h ec o l o r i n gp r o b l e mh a sab i ga p p l i c a t i o n ，a n dw i t ht h e d e v e l o p m e n to ft h ef i e l ds o m es 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 g p 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 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 f c o l o r st o e a c hv e r t e xi 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 sd e f i n et h e c h r o m a t i cn u m b e ro fga sx ( a 1 = 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 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 h e d g e8 0t h a tn ot 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 c n n l b e ri sd e f i n e da sx ( g ) = m i n k g r a p hgh a sk - e d g e c o l o r i n g s t h et o t a lc o l o r i n gi sag e n e r a l i z a t i o no ft h ec o l o r i n ga n dt h ee d g ec o l o r i n g ，a l lo ft h ee l e m e n t s ( v e r t e i c sa n de d g e s ) o ft h eg r a p ha r ec o l o r e di ns u c h aw a yt h a tn 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 o l o r e dt h es a m e i t sa t 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 yv i z i n g ( 1 9 6 4 ) a n di n d e p e n d e n t l yb e h z a d ( 1 9 6 5 ) w i t ht o t a lc o l o r i n gc o n j e c t u r e 2 3 ，2 4 ，2 5 t h ev 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 ga n dt 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 l - o r i n ga r et w on e wc o l o r i n gp r o b l e ma n dw e r ep r e s e n t e db yz h o n g nz h a n g w i t ht w oc o n j e e t u r er e s e n t e l y 2 8 些垄堕堕奎堂雯兰堡堡壅一一 d e f i n i t i o n s u p p o s eg ( v ( g ) ，e ( g ) ) i sag r a p h ， ：i sap o s i t , i v ei n t , e g e r a n dsi sak - e l e m e n ts e tl e tfb eam a pf r o mv ( a ) u e ( a ) t os i f 1 ) f o ra n y 札u ，u 删e ( g ) ，u 1 1 ) ，t h e r ei s ，( 删) ，扣w ) 。2 ) f o ra n y 扎口e ( g ) ，t h e r ea r e ，( u ) ，( u ) ，( u ) f ( u v ) ，( u u ) ，( u ) t h e nfi sc a l l e dak - t o t a le o l o r i n go fg r a p hga n dt h et o t a b c h r o m a t i cn u m b e r i sd e f i n e da sx t ( g ) ( o rd e n o t e da sx ”( g ) ) = m i n k l g r a p hgh a sk - t o t a l c o l o r i n g s i ffa l s os a t i s f i e s 3 ) f o ra n yu ，w y ( g ) ，t h e r ei sg ( 札) c ( v ) ；w h e r eg ( u ) = ，( “) ) u f ( u v ) u v e ( g ) i sc a l l e dt h ec o l o rs e to fv e r t e x “ t h e nfi sc a l l e dav e r t e x d i s t i n g u i s h i n gk - t o t a lc o l o r i n go fg r a p hg ( b r i d i y i t o t e da sk - v d t c ) a n d t ( g ) = m i n k ch a sk - v d t c i sc a l l e d 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 ro fg r a p h g i fc o n d i t i o n3 ) i sc h a n g e dt o 3 7 ) f o ra n y 札口e ( g ) ，t h e r ei sc ( 扎) c ( v ) t h e n ，i sc a l l e daa 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 gk - t o t a lc o l o r i n go fg r a p hg ( i n b r i e f , n o t e da sk - a v d t c ) a n dx 。( g ) = m i n k l gh a sk - a v d t c i s c a l l e dt h e a d j a c e n tv e r t e x d i s t i g u i 8 h i n gt o t a lc h r o m a t i cn u m b e ro fg r a p hg t o t a lc o l o r i n gc o n j e c t u r ef o ra n ys i m p l eg r a p hg ，) ( t ( g ) s ( g ) + 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 o t a lc o l o r i n gc o n j e c t u r e f o r a n ys i m p l eg r a p hg ，x 。( g ) 玉a ( c ) + 3 v 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 gc o n j e c t u r e f o ra n ys i m p l e g r a p hg , k t ( g ) 5x 优( g ) sb ( g ) + 1 , w h e r e 埒( g ) = m i n g l ( 垮+ 1 r k ：6 冬 d ，礼di st h en u m b e ro ft h ev e r t i c e sw i t hd e g r e edi ng r a p hg ) t h ep r o b l e mo fd e t e r m i n i n gt h et o t a lc h r o m a t i cn u m b e ro fag r a p hi sn p h a r d a n dw eo b t a i ns o m er e s u l t e sf o ral o to fg r a p hc l a s s e sa n dg r a p h sw i t h c e r t a i nc o n d i t i o n si nt h i sf i e l d s of a r ，t h es t u d i e so ft h ev e r t e x d i s t i n g u i s h i n g t o t a lc o l o r i n ga n dt 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 l o r i n ga r ef o rt h e 山东师范大学硕士学位论文 s p e c i a lg r a p h s a tp r e s e n t ，t h e r ew e r ef e wr e s u l t sa b o u tf r a c t i o n a lc o l o r i n go fg r a p h s o m e r e s u l t sa r ea b o u tt h ef r a c t i o n a lc h r o m a t i cn u m b e r sa n dm - f o l dc h r o m a t i c n a m b e r so fs o m es p e c i a lg r a p h s ，t h eo t h e ra r ea b o u tw h e t h e rs o m ec o n j e c t u r e i nc o l o r i n gp r o b l e mw e r et r u ei nf r a c t i o n a lc a s e t h et o t a lc o l o r i n gc o n j e c t u r e h a sb e e np r o v e dt r u ei nt h ef r a c t i o n a lc o l o r i n g 1 i nt h i st h e s i s ，t h ef i r s tp a r td e a l sw i t ht h er e l a t i o n sb e t w e e nt h eb a s i c g r a p h sa n dt h e i rm y c i e l s k ig r a p h so rt h ec a r t e s i a np r o d u c tg r a p h so nt h e t o t a ic o l o r i n ga n dt h e ( a 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 g 】a n dw eo b t a i ns o m es n 位c i e n tc o n d i t i o n sw i t hw h i c ht h ec o n s t r u c t i o n a lg r a p h ss a t i s f y t h et o t a lc o l o r i n gc o n j e c t r u ea n dt h ea d j a c e n tt o t a lc o l o r i n gc o n j e c t r u et h e s e c o n dp a r tf o c u s e so nt h em b o l dc o l o r i n go ft h ek n e s e rg r a p h sa n dac i r c n l a n tg r a p hg n6f i r s t l yt h em b o l dc o l o r i n gn u m b e ro fg n ，6g r a p hh a sb e e n d e t e r m i n e dc o m p l e t e l yb u tt h ek n e s e rg r a p h sh a v e n ts e c o n d l yi ts t u d i e s t h ef r a c t i o n a lc o l o r i n go ft h ec a r t e s i a np r o d u c tg r a p h sa n dt h ef r a c t i o n a l t o t a lc h r o m a t i cn u m b e ro fs o m es p e c i a lg r a p h s ( f o re x a m p l e ：c y c l e ，c o m p l e t e g r a p h ，c o m p l e t eb i p a r t i t eg r a p h ，b a l a n c e dc o m p l e t er p a r t i t eg r a p h ) w eb r i e f l vs u m m e r i z eo u rm a i nr e s u l t sa sf o l l o w ： w ec a l lt h eg r a p ho b t a i n e db yt h em y c i e l s k ic o n s t r u c t i o n 2 1 t h em y c i e l s k ig r a p h g i v e nag r a p hgw i t hv ( c ) = v l ，v 2 ，) ，t h em y c i e s k i g r a p h ( d e n o t e db yn 扩( g ) ) o fg i sd e f i n e dt ob eag r a p hw i t hv ( 彳( g ) ) = v u u i ， ：，- 一，w ：，u ) a n de ( m ( g ) ) = e ( g ) u v i v i v i v j e ( g ) ，i ，j = 1 ，一，札) u u ；“1 。= 1 ，一，n ) t h e o r e m2 1 1 s u p p o s eg i sag r a p hw i t hnv e r t i c e s i fx r ( a ) n ，t h e n x t ( w ( g ) ) s ) i t ( g ) + a ( a ) ；i fx t ( g ) 1 i sap o s i t i v e i n t e g e r i fn ( c ) + 2 x 。t ( g ) ( g ) + ka n dx ( h ) sa ( c ) + k ，t h e n 山尔师范火学硕十学付论文 ) ( 。t ( g h ) s ( g h ) + 七+ 1 c o r o l l a r y2 2 5s u p p o s eg 日a r et w og r a p h s a n d 1i sap o s i t i v e i n t e g e ri f 。f ( g ) ( g ) + 2a n d ) ( ( 日) ( g ) ；t h e ngx 日s a t i s f i e st h e 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 o t a lc o l o r i n gc o n j e c t u r e s u p p o s er = u l u 2 u na n d p , z = v l v 2 训na r et w op a t h s l e t 8o v e r l a y m a t c h i n g s g i r l ，“t 仇+ l ， ：札t + 凫，u i v i + ( n 一1 1 b e t w e e nt h et w op a t h ss u e c e s s i v e l y ( i = l ，2 ；- ，n ，k = 0 ，1 ，一n 一1 ，g e tm o dnw h e ni + k 几+ 1 ) s o w ec a no b t a i nas e q u e n c eo fg r a p h s ：p 麓：p 裂，磁譬”，碟皇= rvp n s u p p o s ev l = 姐1 ， 9 2 ，- ：札n ) ，k = 刨l ，? 3 2 ，u n ) ，u l u 2 u n “1 a n d 1 2 2 v n u ia r et w oc y c l e s s i m i l a r l y , w eo v e r l a yt h ea b o v em a t c h i n g sb e t w e e n t h eb i p a r t i t i o n ( ，k ) s u c c e s s i v e l y as e q u e n c eo f r e g u l a rb i p a r t i t eg r a p h s ：g 黜 g 瓣，g 瓣”，g 瓣= 。c a nb eo b t a i n e d w ec a no b t a i nas e q u e n c e o fr e g u l a rg r a p h s 咄，嗽，c 蝣1 ，m c o m o = gvg b yo v e r l a y i n gt h e a b o v em a t c h i n g sb e t w e e nt h et w oc y c l e s t h e o r e m2 3 1 x a t t ：群廿1 ) ) = ( 群等1 ) + 2 = 女+ 5 ( k = 0 ，1 1 ，n 3 ) t h e o r e m2 3 2 ) c 。( g 譬； 1 ) = ( g 釜：1 ) + 2 = k + 3 ( 惫= 0 ，l l ，n 3 ) c o r o l l a r y2 3 3 斯( 群1 ) ( 群1 ) + 2 ，x r ( g 瓣1 ) 茎( g 滋1 ) + 2 , t h a ti st os a y 碟材1 ) a n dg 黠”s a t i s f yt h et o t a lc o l o r i n gc o n j e c t r u e ， t h e o r e m2 3 4 x t ( g 古1 ) 一a f t v 。( k 。+ 1 ) + 2 = 惫+ 5 ( 七= 0 ，l 1 ，n 兰3 ) t h e o r e m2 3 5 x 。( g ，。) = 5 3 ) 讥 山东师范大学硕士学位论文 t h e o r e m2 3 6 地c 吲= 一答 t h e o r e m2 3 8l e tgb eag r a p hw i t he d g e c o n n e c t i v i t ya ( g ) = 1 ，s u p p o s e 札o ”ob ea n yc u t e d g e ，g l ，g 2b ec o n n e c t e dc o m p o n e n t so fg r a p h g 一“o v oa n d o v ( a t ) ，v o v ( c 2 ) t h e n fa ( c ) + 2d ( u o ) = d ( v o ) = z x ( c ) ，) ( 。l ( 0 1uu o v 0 ) ) ( “( g ) = = x 。t ( uu o v 0 ) = a ( c ) + 1 【m a x x 。( g 1u “0 v 0 ) ，) ( 。t ( g 2uu o v o ) o t h e r w i s e i nf o l l o w i n gw ew i l li n t r o d u c et w oi m p o r t a n tg r a p h s ：k n e s e rg r a p h sa n d g n6g r a p h s u p p o s e 2 b ，a ，ba r et w op o s i t i v ei n t e g e r s t h ek n e s e rg r a p h 虬bh a sv e r t i c e sa l lt h eb - s u h s e t so faa - s e t ，a n dt w ov e r t i c e sa r ea d j a c e r t ti f a n do n l yi ft h et w os u b s e t sa r ed i s j o i n tt h eg r a p hg b 2 9 w h i c hi ss p e c i a l c i r c u l a n tg r a p hh a sv e r t i c e s0 ，l ，- ，o 1 ，a n dt h ev e r t i c e si ，ja r ea d j a c e n t i fa n do n l yi fb 1 2 一j l 曼a bk n e s e rg r a p h sa n dg 。9g r a p hr e s p e c t i v e l y p l a yi m p o r t a n tr o l e si n t h ef r a c t i o n a lc o l o r i n ga n dt h ec i r c u l a rc o l o r i n g ，w h a t c o m p l e t eg r a p h sp l a yi nt h eo r d i n a r yc o l o r i n g s t a h l 1 7 1p r o p o s e dt h ec o n j e c t r u e ：f o ra n yp o s i t i v ei n t e g e rm ：x m ( 尺。b ) = a 一2 b + 2 mi st r u e 1 4 1h a sb e e np r o v e dt h ec o n j e c t r u ei st r u ef o r1 m 6 a n dt h ef o l l o w i n gt h e o r yw i l l 、p r o v et h ec o n j e c t r u ei sw r o n gf o rm b t h e o r e m3 1 1w h e na 2 b ，m b , x m ( k n ：。) a 一2 b + 2 m t h e o r e m3 1 2x m 6 ( 。b ) = g r t a ( a ，b ，ma r ep o s i t i v ei n t e g e r s ) t h e o r e m3 1 4s u p p o s ea ，b ma r ep o s i t i v ei n t e g e r s 。( g “) = x ( c 。，6 ) = f 警1