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

独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得( 注：如 没有其他需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材 料。与我同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意。 学位论文作者签名：王丽1 书 导师签字：砚磊 学位论文版权使用授权书 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权堂撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名：王丽1 书 签字日期：2 0 0 8 年辱月弓日 导师签字：热磊 签字日期：2 0 0 8 年千月2 弓日 山东师范大学硕士学位论文 图的邻点可区分的全染色 中文摘要 染色问题及许多图理论都是源自四色问题的研究另外染色问题在组合分析和 实际生活中有着广泛的应用，是图论研究中一个很活跃的课题，各类染色问题被相 继提出并加以发展、应用 图g 的一个( 正常) 七- 染色【1 】是将詹种染色分配给g 的顶点集v ( g ) ，使得相 邻两顶点的颜色不同定义色数为：x ( g ) = m i n 例图g 有南- 染色 类似的，图 g 的一个( 正常) 七- 边染色【1 是将后种染色分配给g 的边集e ( g ) ，使得有公共端 点的两边的颜色不同边色数x 7 ( g ) = m i n 纠图g 有七一边染色】 全染色的概念是对点染色和边染色的推广，图的所有元素( 顶点和边) 都将染 色且任相邻或关联的元素染色不同全染色是图论染色的一个传统问题，由v 江 i n g ( 1 9 6 4 ) 【2 3 】和b e h z a d ( 1 9 6 5 ) 【2 4 2 5 】各自独立提出的，同时分别给出全染色猜想 点可区分全染色和邻点可区分全染色是染色问题的新生点，近来由张忠辅老师提出 并给出了相应的两个猜想 定义【2 】设g ( ke ) 为图，良为正整数，s 为七色集，令映射，：y ( g ) j e ( g ) 一 s 如果 ( 1 ) 对任意u t ，” e ( g ) u 叫有，( u ) ，( u ) ； ( 2 ) 对任意u t i e ( g ) ，有，( 乱) ，( t ，) ，( u ) ，( 乱”) ，( 札t ，) 厂( 口) ， 那么称厂为图g 的一个后全染色若还满足 ( 3 ) 对任意 牡：可y ( g ) ，c ( u ) c ( t ，) ，其中c ( t ) = ，( 乱) u ，( t 正钉) 札t 。e ( g ) ) ： 那么称，为图g 的一个点可区分的岛全染色( 简记为矗一y d 丁c ) 若条件( 3 ) 改为 ( 3 7 ) 对任意乱 e ( g ) ，c ( 札) c ( t ，) ， 那么称，为图g 的一个邻点可区分的“全染色( 简记为克a y d 丁c ) 图g 的全色数x 丁( g ) ( 或记为x ”( g ) ) = m i n 俐图g 有“全染色) 图g 的点 可区分的全色数x 优( g ) = m i n 后i 图g 有七y d t c ，图g 的邻点可区分的全色数 山东师范大学硕士学位论文 x n ( g ) = l n i n 岛i 图g 有七- a y d 丁c ) 全染色猜想 1 3 】对任意简单图g ，x 丁( g ) ( g ) + 2 点可区分的全染色猜想对简单图g ，七t ( g ) x 优( g ) 七丁( g ) + 1 ；其中 七丁( g ) = m i n 川四十1 n d ，6sd m d 是度为( f 的顶点数) 邻点可区分的全染色猜想 2 】对简单图g ，x n t ( g ) ( g ) + 3 张忠辅老师给出了邻点可区分全染色的两个引理 对任意阶为n ( n 2 ) 的简单图g ，邻点可区分的全色数x 叭( g ) 存在，并且 x 耐( g ) ( g ) + 1 若图g ( 矿e ) 有两个相邻的最大度点，则有x d f ( g ) ( g ) + 2 确定一给定图的全色数是n p 一困难的，目前已对许多图类( 如：完全图，二部 图，完全r 一部图、部分正则图、平面图等) 和满足一定条件的图得到了一些结论 邻点可区分全染色目前只有关于特殊图的结果，例如：完全图、完全二部图、星、 扇、轮及它们的联图；另外邻点可区分全染色问题对树和上述特殊图的m y c i e l s k 图 2 1 】、乘积图 2 0 有一些结论 在本文中，我们主要得到结论如下： 令s ，f ? 且1 f u 一1 ) u 饥伽i i i = o 1 ，2 ， ，s 一1 u 妣q ：忙一j i 。= f ) ，其中i t 一乩三l 一歹i ( m d ds ) 2 定理2 1 1 对推广的p e t e r s e 钆图，有) ( 口( p ( s ，f ) ) = 5 ，s 2 f ，f 1 2 ，忌= 1 ，2 山东师范大学硕士学位论文 以下结论是关于推广的尸e t e r s e 礼图邻点可区分全染色的推广，对推广的p e t e r s e n 图尸( s ，f ) o 砚一1 构成一个圈c 令圈c 7 = i t ：一1 和圈c = 硝口? u 2 1 是圈c 的两个复制，且连接口。，t i ：和u 孙= o ，1 ，s 一1 ，则得到新图g 引理2 1 2 图g 如上定义，有x 。( g ) = 6 定理2 1 3 对推广的p e e r s 鲫图p ( s ，f ) ，圈c = 如u 1 一1 有m 个复制，且连 接u ； ：其中i s 一i = 1 ，o s m 得到新图g 则x n ( g ) = 6 令g 1 g 2 是互不交的后临界图( 蠡4 ) 令日1 j 飓是g 1 g 2 中的一个完全二 部图且y 1 ，2 是g l 一日1 ，g 2 一g 2 中与日1 ，啦中顶点z 1 ，z 2 相邻的一个顶点粘合 g 1 ，g 2 成一个新的完全二部图日，使得z l ，z 2 粘合为一点，删除边z l 妙1 z 2 剪2 连接 耖l ，耖2 成一条新边，从而得到新图g 【1 4 令= k 1 v g ，1 7 ( k ) = u 1 ，现：u n ， o ) e ( ) = 似u 件l k = 1 ，佗：+ 1 = u 1 ) o 如地k = 1 ，n ) w 为w 么的复制 定理2 2 1 推广的日口7 缸s 札m 名= ( u l u 2 ) + ( w 名u i 可5 ) 粘合口1 也u i 钞；为 一条边，删除边 2 u ；喀连接呓则 地c 叫蠢i 卵4 定理2 2 2 推广的日叮钿s 扎m 崂= ( ，如u 1 ) + ( t ，i ) ，粘合如钞1 t ! i 为 一条边，删除边叩f 2 t ，i t ，0 连接也，呓，则 ) ( 酊( 畎) = 2 九 3 山东师范大学硕士学位论文 定理2 2 3 推广的日幻由s u m ，n = ( p t 7 1 2 ) + ( w ：口i 口；) ，粘合u l 口2 ，u i u ； 为一条边，删除边 2 u ；u ；，连接口3 ，u 3 ，则 x n f ( 陈，。) - 7 l in + 1 定理2 2 4 推广的日幻如s 札mg = ( ，口。一1 ) + ( 一1 u 麓) ，m ，n24 ，粘合 口n 1 可幺一l 知为一条边，删除边u 。r ：n i ：连接钉i 则 x o t ( g ) = m + 咒一2 在含有”个顶点的路孙上，当且仅当两点距离为角时添加一条边，所得的图 称为璐我们给出了部分磁图的邻点可区分的全色数 定理2 3 1 对图璐! 有) ( 口t ( 磁) = 6 ，膏 1 m 2 忌+ 2 下面的部分将涉及到一类重要图：k ( n m ) 定义如下；若图g ( k e ) 满足； ( 1 ) y 的点是由从一集合彤= n ，n 2 ，口礼) 任意抽取m 个元素所组成的点， 点记为u = ( n 。l ，n t 2 ，o l 。) ， l ，t 2 ，t m 1 2 ，n ) ； ( 2 ) 比= 铡，8 e ，当且仅当珏= ( 啦，8 ，8 。) ， = ( 8 ：。，口：。：，8 ：。) 中的 中吼。，n 幻：o t m ，n ：。，o ：。，口，m 没有相同元素，称之为k e s e 7 n 图，记为k ( 礼，m ) 【1 8 4 定理2 4 1x 。( k ( 5 ，2 ) ) = 5 定理2 4 2x 口( k ( 6 ，2 ) ) = 8 山东师范大学硕士学位论文 定理2 4 3x 疵( k ( 7 ，2 ) ) = 1 1 关键词：邻点可区分全染色；推广的p e e r s e ”图；推广的日幻幽s 乱m ；磁图； k e s e r n 图 分类号： 0 1 5 7 5 5 山东师范大学硕士学位论文 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 ht o t a lc o l o r i n go fg r a p h s a bs 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 印ht h e o r i e sa r ea 1 1f r o mt h es t u d y o ft h ec e l e b r a t e df 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 a lm a t h e m a t i c sa n do u r l i v i n g ，t h ec 0 1 0 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 ed e 、r e l o p m e n to ft h e f i e l ds o m esc ：h o l a r sp r e s en _ 乞e da n ds t u d i e daf 色wc o l o r i n gp r o b l e m sw i t hd i f k r e n t r e s t r i c t i o n a ( p r o p e r ) 七一c 0 1 0 r i n go fg r a p hg 1 】i sa na s s i g n m e n to fo n eo f 豇c 0 1 0 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 mv e r t i c e sh a v ed i s t i n c tc o l o r s d e 矗n et h ec h r o m a t i c n u m b e ro fga sx ( g ) = m i n 艮l g r a p hg h a s 良- c o l 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 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 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 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 丘n e da s ) l 7 ( g ) = 1 i n 七l g r a p hgh a s 七一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 0 1 0 r i n ga n dt h ee d g ec o l o r i n g a l l o ft h ee l e m c n t s ( v e r t e i c sa n de d g f s ) o ft h eg r a p ha r ec o l o r e di ns u c haw a 、t h a t n ot w oa d j a c e n to ri n c i d e me l e m e n t sa r ec o l o r e dt h es a m e i t sat r a d i t i o n a l lc o l o 卜 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 ) a n di n d e p e n d e n t l yb c h z a d ( 1 9 6 5 ) w i t ht o t a lc o l o r i n gc o l l 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 0 1 0 r i n ga n d t h ea ( 1 j a c e r l tv e r t e x d i s t i i l g u i s h i i l 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 la n d w e r ep r e s e n t e db yz h o n g f uz h a n gw i t ht w oc o n j e c t u r er e s e n t e l v d e f i n i t i o n 【2 】 s u p p o s eg ( y ( g ) ，e ( g ) ) i sag r a p h ，岛i sap o s i t i v ei n t e g e ra n d si sa 缸e l e m e n ts e t l e t ，b eam a pf r o my ( g ) ue ( g ) t os i f 1 ) f o ra n y 让 ，u 叫e ( g ) ，t 正叫，t h e r ei s 厂( t 正u ) ，( 口t u ) ； 2 ) f 6 ra 1 1 y 仳t ，e ( g ) ，t h e r ea r e ，( 乱) 厂( u ) ，( 乱) 厂( 乱u ) ，厂( u ) ，( u ) ， t h e n 厂i sc a l l e da 七一t o t a lc o l o r i n go fg r a p hg a n dt h et o t a l c h r o m a t i cn u m b e ri s d e f i n e da sx t ( g ) ( o rd e n o t e da sx ( g ) ) = m i n 尼i 铲a p hgh a s 七一t o t a l - c 0 1 0 r i n g s i f 。，a l s os a t i s f l e s 6 山东师范大学硕士学位论文 3 ) f o ra n y 乱，r y ( g ) ，t h e r ei sc ( “) c ( t ) ：w h e r ec ( 乱) = ，( t 上) 】u - 厂( “t ，) i u r 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 n 厂i sc a l l e dav 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 go fg r a p hg ( b r i e f l ) n o t e d a s 七一v d t c ) a n d 入。( g ) = m i n 后 gh a s “、t c ) i sc a l l e dv 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 ( 、n u 证b e ro fg r a p hg i fc o n d i t i o n3 ) i sc h a n g e dt o 3 ，) f o ra n 、u f e ( g ) t h e r ei sc ( u ) c ( 口) ， 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 g 七一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 s 七一a 、厂d t c ) a n dx o t ( g ) = m i n 足i gh a s 矗一a v d t c ) i sc a l l e 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 h r o m a t i cr m 1 b e ro fg r a p hg t o t 址c o l o r i n gc o n j e c t u r e 【1 3 】f o ra n ys i m p l eg r 印hg ，) ( 丁( g ) f g ) + 2 、厂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 幻( g ) s ) ( 优( g ) 七丁( g ) + 1 w h e r e 忌丁( g ) = m i n ? i 凹+ 1 礼d 6 d n di st h en u i n b e ro ft h ev e r t i c e s 诵t hd e g r e edi 1 1g r a p hg ) a d j a c e n tv 6 r t e x d i s t i n g u i s h i n g r o t a lc o l o r i n gc o n j e c t u r e 【2 】f o ra n y s i m p l eg r 印hg ，x 口c ( g ) ( g ) + 3 z h a n gz h o n g f up r e s e n t e dt w oi m p o r t a n tr e s u l t sa b o u tt 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 m n b e ro fg r a p hg f o ra l ws i m p l ec o n n e c t e dt w oi m p o r t a n tg r a p hgo fo r d e rn ( n 2 ) 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 i n gt o t a lc h r o m a t i cn u l b e r ) ( o t ( g ) e ) c s i t s ：a n dx 口t ( g ) ( g ) + 1 i fg ( 矿e ) h a st w oa d j a c e n tm 觚i l u md e 黟e ev e r t i c e s t h e n ) ( 口( g ) ( g ) + 2 t h ep r o b l e mo fd e t e r i i l i n i n gt h et o t a lc h r o m a t i cn u i n b e ro fag r 印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 hc e r t a i n c 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 gt o t a lc o l o r i n g a 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 g sa r ef 6 rt h es p e c i a lg r a p h s ，f o r e x a m p l e ：m y c i e l s k ig r a p h sa n dt h ec a r t e s i a np r o d u c tg r a p l l s 7 山东师范大学硕士学位论文 w ab 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 sf o l l o w ： l e ts ，f a n d1 sf 2 f ，f 1 2 七，七= 1 ，2 ，t h e nx n f ( p ( s f ) ) = 5 t h ef 0 1 l o w i n gr e s u l t sa r ea b o u tt h eg e n e r a l i z e da 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 ft h eg e n e r a l i z e dg r a p hp e z e r s e 竹p ( s f ) 】珀rg e n e r a l i z e dg r a p h 尸e e r s e 礼尸( s ，z ) ，c = 如 1 一1i sac y c l e l e tc 7 = u ；u i f ：一1a n dc = u ：f ? u 殳1a r et ，oc o p i e so fc g r a p hgc a nb eo b t a i n e db ya p p l i c a 七i o no ft h e f 6 l l o w i n go p e r a t i o n ：j o i nu t ：r ；a n du ：t 7 7 ， = o 1 ：，s 1 l e m m a2 1 2 g r a p hgi sd e f l n e da s r ej u s ts a i d ，t h e n ) ( 越( g ) = 6 t h e o r e m2 1 3f b rg e n e r a l i z e d 静a p hp 酎e r s e 礼p ( s ：f ) ：c y c l ec = 1 一1 h a sm c o p i e s j o i n tr ；。：w h e ni s t i = 1 o s ：芒m ，s ot h a tw ec a no b t a i na n e wg r a p hg a n d ) ( d ( g ) = 6 l e tg l 口n dg 2b ed i s j o i n t “c r i t i c a lg r a p h s ( 七4 ) f o ri = 1 2 。l e t 日fb ea c o m p l e t e2 - g r a p hi ng t f o ri = l ，2 ，l e t 玑b eav e r t e xo fg 一日 j o i n e dt oav e r t e x z zo f 且o b t a i ngf r o mg 1a n dg 2b yi d e n t i 如i n g 研a n d 飓t oan e wc o m p l e t e 2 。g r a p hh s ot h a tz 1a n dz 2a r ei d e n t i 矗e d ，d e l e t et h ee d g e sz y la n dj o i ny 1a n d 沈b yan e we d g e 1 4 】 l e t 眠= k 1 v g ，y ( ) = 钉l ，也， o ) ，e ( ) = 耽+ l k = 1 ，n ； t ，n + 1 = 即1 ) u t ，o 仉i i = 1 ，n ) ，i nw h i c h 名i sac o p yo f 么 8 t h e o r e m2 2 1g e n e r a l i z e dh 町以s u m 孵= ( ，秽l 忱) + ( 孵，f i 呓) ，i d e n 山东师范大学硕士学位论文 t i 母t 1 1 秒2 ：u i f ：t oan e we d g e ，r e m o v eu 2 u 3 f ；t a n dj o i n t 秽3 f ；t h e n f ”+ 1 礼6 i 入。，( 公) = 7 咒= 5 i 【6 扎= 3d r4 t h e o r e m2 2 2g e n e r a l i z e d 日d 歹西s u m1 1 z = ( ，n 如2 ，1 ) + ( 1 1 z u j t ) i d e n t i 母u o u l7 可；f it oan e we d g e ，r e m o v et j l u 2 秽i 可；，a n dj o i n tu 2 可；，t h e n 入口f ( ，公) = 2 n t h e o r e m2 2 3 g e n e r a l i z e d n 6 ss u 玎篙扎= ( 仇，竹。，t ，1t j 2 ) + ( z t j i t 乏) ， i d e n t i 岛u 1u 2 口：秽；t oan e we d g e r e m a v eu 2 u 3 。；u ；a n dj o i n tu 3 ，u ；t h e n x 耐c i m ，= 三+ 1 三三圣三。i s t h e o r e m2 2 4 g e n e r a l i z e d n 歹6 5s “mg = ( _ ：u 竹一1 口n ) + ( j 。，u ：n l t ：。) ， l ，n 4 ，i d e n t i 玲秽n 一1 f 佗，u 二一1 t 幺t oan e we d g e r e m 。v ef 几u l ，u 名u i ，a n dj o i n t 秒1 ，u i ， t h e n x 。( g ) = m + n 一2 9 山东师范大学硕士学位论文 t h e o r e m2 3 1f o rg r a p hj p 尝，i f 后 1 n 2 詹+ 2 t h e n ) ( 口( f 尝) = 6 t h ef 0 1 1 0 w i n gr e s u l t sa r ea b o u tk ( n ，m ) g r 印h e s e r 咒k ( 九，州【1 8 】( 1 ) h a sv e r t i c e sa l lt h em s u b s e t so fas e tw = f 1 n 2 ，o 礼) t h ev e r t i c 村i sd e n 。t e db y ( 8 n ，8 。2 ，。f m ) ，童1 主2 ，i 7 ，l 1 2 ， n ) ： ( 2 ) f o re = u u ：ei ne n 小o ，o 新n ：l ，n ：2 ，o ：mi i l “= ( o ”o t 2 ，口。m ) ：t = ( n ：1 q 一，n ：。) a r ea l ld i f f r e n t s t h e o r e m2 4 1 x 。( k ( 5 2 ) ) = 5 t h e o r e m2 4 2 ) ( 口( k ( 6 ，2 ) ) = 8 t h e o r e m2 4 3 x 。t ( k ( 7 ，2 ) ) = 1 1 k e yw o r d s ：t h ea ( 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 g t h eg e n e r a l i z e dg r a p hp e f e r s e n t h e g e n e r a l i z e d 日n 歹6 ss u m ：g r a p hf 尝，g r a p h e s e r n 1 0 c l a s s i f l c a t i o n ：0 1 5 7 5 山东师范大学硕士学位论文 第一章引言 染色问题及许多图理论都是源自四色问题的研究，四色问题在其被探讨的百年 期间大大推动了图论的发展另外染色问题在组合分析和实际生活中有着广泛的应 用，是图论研究中一个很活跃的课题，各类染色问题被相继提出并加以发展、应用 一个图g 是指一个有序对g = ( y ( g ) e ( g ) ) 其中y ( g ) 是顶点集，e ( g ) 为边集，e ( g ) 中的边为y ( g ) 中两不同顶点的无序对若i ( g ) 中的两顶点札川 之间有边，则称两顶点相邻且互为邻点，边记为u u ，称边u u 关联u ，u ，边让z ，的端 点为u ：掣若两边有公共端点，则称两边相邻且互为邻边端点重合为一点的边称 为环；若两边有相同的两个端点，则称它们为多重边一个图为简单图，若它既没 有环也没有多重边本文所讨论的图均为简单、有限图 图g 到图日的一个同态指映射厂：v ( g ) 一y ( 日) ，使得删e ( g ) 时 ，( z ) f ( 可) e ( h ) 两图g 和日称为同构的( 记为g 兰h ) ，如果存在两个一一映 射口：1 7 ( g ) 一y ( 日) 和口：e ( g ) 一e ( 日) 使得西( u 口) = 臼( 乱) 口( ”) 自同构是指 一图到它自身的一个同构 日( y 7 e 7 ) 称为图g ( ke ) 的子图，若至i e 7 e 假设y 7 是v 7 的一个 非空子集，以v 7 为顶点集，以两端点均在1 ，中的边的全体为边集所组成的子图， 称为g 的由y 7 导出的子图，记为g 1 ， ：g 【称为g 的导出子图g e 表示从 g 中去掉边e 得到的图对任意u l 厂( g ) d ( r ) 表示顶点t ，在g 中关联的边数， 称为t 的度定义6 ( g ) = m i n d ( u ) l u i ，( g ) ) ( g ) = m a d c d ( u ) i u y ( g ) ) ，分 别称为g 的最小度和最大度y ( g ) 的子集s 称为独立集，若s 中的任意两顶点 均不相邻顶点数最多的独立集称为g 的最大独立集，顶点个数称为独立数，记 为q ( g ) 简单图g 的一个团是指顶点集的一个子集s 使得g f 别是完全图顶点 数最多的团称为g 的最大团，顶点个数称为g 的团数，记为u ( g ) 【z j 表示不大 于实数z 得最大整数， z 表示不小于实数z 的最小整数旧表示集合s 中元 素个数 图g 中的途径是一个有限非空序列u = 咖e 1 秽l e 2 现e 七，它为顶点和边的 交错序列，且龟( 1 is ) 的端点为饥一l ，饥，途径的长为庇若u 中u o ，u 1 ，讥 两两不同，则称它为路，简记为u o 1 讥起点和终点重合的路称为闭路或圈，简 记为 o 秽1 坝t j o g 中的两个顶点称为连通的，如果在g 中两顶点间有路若g 的所有顶点都互相连通，则称g 是连通的，否则称为不连通且称g 的每个极大连 1 1 山东师范大学硕士学位论文 通部分为它的分支割边是指使得g e 的连通分支数大于g 的分支数的边e 对 i ，的子集5 和s 7 用限s 7 表示一个端点在s 中，另一个端点在s 7 中的所有边 的集所谓g 的边割是指形为阻剐的e 的子集，其中s 是y 的非空真子集， 且s = v s 一个七边割是指有七个元素的边割g 的所有七边割中最小的七定 义为g 的边连通度k 7 ( g ) g 平凡或不连通时k ( g ) = 0 ：g 是含有割边的连通图时 k 7 ( g ) = 1 所有顶点均两两相邻的简单图称为完全图，扎个顶点的完全图记为k 设 l j ，k 是图g 的两顶点独立集，若1 7 ( g ) = kuk ，nk = o ，则称g 为二部图 或偶图；进一步，若中的每个顶点与k 中的每个顶点相邻，则称g 为完全二 部图，此时若i k l = 礼，i k f = m 则记为m 图g 的一个( 正常) 七一染色是将忌种染色分配给v ( g ) ，使得相邻两顶点的颜 色不同定义色数为：x ( g ) = 耐n 七l 图g 有后一染色 类似的，图g 的一个 ( 正常) 艮边染色是将七种染色分配给e ( g ) ，使得有公共端点的两边的颜色不同 边色数) ( 7 ( g ) = i n i n 七i 图g 有七一边染色) 显然) ( 7 ( g ) ( g ) ，且已证明对二部 图等号成立 2 8 】 邻点可区分全染色 全染色的概念是点染色和边染色的推广，图的所有元素( 顶点和边) 都将染 色且任相邻或关联的元素染色不同全染色是图论染色的一个传统问题，由z - i n g ( 1 9 6 4 ) 2 3 和b e h z a d ( 1 9 6 5 ) 2 47 2 5 】各自独立提出的，同时分别给出全染色猜想 点可区分全染色和邻点可区分全染色是染色问题的新生点，近来由张忠辅老师提出 并给出了相应的两个猜想 定义1 1 2 】设g ( ke ) 为图，后为正整数，s 为七一色集，令映射，：v ( g ) u e ( g ) 一s 如果 ( 1 ) 对任意u u ，口协e ( g ) ? u 叫：有，( u u ) 厂( 可叫) ； ( 2 ) 对任意札u e ( g ) ，有，( 札) ，( 口) ，t 厂( 仳) ，( 乱钉) ，( u 可) 厂( ) ， 那么称，为图g 的一个后一全染色若还满足 ( 3 ) 对任意札，u y ( g ) ，c ( u ) c ( u ) ，其中c ( 乱) = ，( u ) ) u ，( u u ) l u u 1 2 山东师范大学硕士学位论文 e ( g ) ， 那么称，为图g 的一个点可区分的七一全染色( 简记为“1 7 d 丁c ) 若条件( 3 ) 改为 ( 3 7 ) 对任意u 可e ( g ) c ( u ) c ( 秽) ， 那么称，为图g 的一个邻点可区分的后- 全染色( 简记为膏一a r d 丁c ) 图g 的全色数灭r ( g ) ( 或记为入“( g ) ) = n 血 岛1 图g 有七一全染色) 图g 的 点可区分的全色数) ( 优( g ) = 1 1 1 i n 七i 图g 有“1 7 d 丁c 图g 的邻点可区分的全 色数入。t ( g ) = m i n 七i 图g 有七一a l d 丁c ) 图g 的全图丁( g ) 的顶点集为y ( g ) ue ( g ) 此顶点集中两顶点间有边当且 仅当它们在图g 中相邻或关联可见图g 的全色数x “( g ) ) 就是全图丁( g ) 的色 数) ( ( 丁( g ) ) 我们称全图丁( g ) 的独立集为图g 的全独立集，丁( g ) 的团为图g 的全团对任意简单图，易见x 丁( g ) ( g ) 1 v i z i n g ( 1 9 6 4 ) 和b e h z a d ( 1 9 6 5 ) 各 自独立给出全染色猜想 2 3 2 4 2 5 全染色猜想1 2 1 3 对任意简单图g x 丁( g ) ( g ) 二2 点可区分的全染色猜想【2 4 】对简单图g 尼丁( g ) s 入价( g ) 昆丁( g ) + 1 ：其中 膏丁( g ) = m i n f i 口+ 12m 6 d n d 是度为d 的顶点数) 邻点可区分的全染色猜想1 3 2 j 对简单图g x n ：( g ) ( g ) + 3 图的邻点可区分全染色有两个重要的引理 引理1 1 【5 对任意阶为n ( n22 ) 的简单图g 邻点可区分的全色数x n f ( g ) 存 在，并且 ) ( 砒( g ) ( g ) + 1 引理1 2 【5 】若图g ( ve ) 有两个相邻的最大度点，则有) ( 。( g ) ( g ) + 2 确定一给定图的全色数是n p 一困难的，目前已对许多图类( 如：完全图、二部 图、完全7 - 部图、部分正则图、平面图等) 和满足一定条件的图得到了一些结论 1 3 山东师范大学硕士学位论文 例如；1 9 9 2 年，y a p 和c h e w 【3 0 证实了( g ) n 一5 时任意n 阶图g 满足全 染色猜想1 9 9 3 年，h i i t o n 和h i n d 3 1 j 证明( g ) 2 ；n 时任意n 阶图g 满足 全染色猜想 1 9 9 7 年，b o r o d i n k o s t o c h k a 和、6 0 d a l l 【3 2 得到( g ) 1 1 时任 意平面图g 的全色数为( g ) + 1 当( g ) 5 时，也已证明任意图g 满足全染 色猜想f 3 3 i 邻点可区分全染色目前只有关于特殊图的结果，例如：完全图、完全 二部图、星扇、轮及它们的联图；另外邻点可区分全染色问题对树和上述特殊图 的m y c i e l s k i 图、乘积图有一些结论 第二章主要是讨论了推广的尸e e r s e 图和推广的h n 歹钿s 伽r 】图的邻点可区 分的全染色方面；另外还得到了特殊图类( 如：磺，k e s e r n 图) 在此染色方面的一 些结果 1 4 山东师范大学硕士学位论文 第二章主要结果 本章主要是探讨了推广的p e t e r s e 竹图和推广的日n j i 曲s u m 图的邻点可区分 的全染色方面；另外还得到了特殊图类( 如：磺： ，e s e r n 图) 在此染色方面的一些 结果 2 1推广的j p e e r s e ”图的邻点可区分的全染色 在图论中，p e e r s e 礼是最为著名的图本文中把尸e e r s e 礼推广为一类图 本文只考虑简单图 令6 ? 且l 7 2 f f 1 2 七五。= 1 2 证明：因为( p ( s f ) ) = d ( u o ) = d ( 一1 ) = 3 且u o 一1 e ( g ) 由引理1 2 知 入口f ( p ( s f ) ) 5 下给出尸( s f ) 一个5 一。4 l7 d 丁c 令，：7 ( 尸( s ，) ) ue ( 尸( s ，f ) ) _ 1 2 ，3 4 5 ) 1f 是奇数时 ( 1 ) s 兰1m o d 2 1 7 f = 1 用2 1 循环染，叫t 用1 2 循环染， 厂( 耽毗) = 5 ，i = 0 71 ，s 一 2 u o u l ，秒。一3 一2 用3 ，4 循环染，( u 。一2 f 。一1 ) = 2 ，厂( f 。一1 u o ) = 4 ，( 一1 ) =