若干图的Mycielski图的点可区别均匀边色数

第38卷 第2期西南师范大学学报(自然科学版)2013年2月V o l .38 N o .2 J o u r n a l o f S o u t h w e s t C h i n aN o r m a lU n i v e r s i t y (N a t u r a l S c i e n c eE d i t i o n )F e b .2013文章编号:10005471(2013)02002504冠图C m ㊃S n 和C m ㊃P n 的邻点可区别I 全色数①田京京陕西理工学院数学系,陕西汉中723000摘要:根据冠图C m ㊃S n 和C m ㊃P n 的结构性质,用穷染递推的方法,讨论了C m ㊃S n 和C m ㊃P n 的邻点可区别I 全染色,得到了相应的色数,并给出了具体的染色方案.关 键 词:图;星;路;冠图;邻点可区别I 全染色;邻点可区别I 全色数中图分类号:O 157.5文献标志码:A图的染色问题是图论研究的主要内容之一.它有着很重要的实际应用背景,无论是电信通讯站点的频率分配问题,还是人力资源配置问题都与图染色有着重要的联系.目前,图的染色理论被广泛应用于计算机网络结构区分,计算机和银行安全密码问题等方面.而图的染色的基本问题就是确定其各种染色法的色数[1-11].为了解决网络权的分配问题,文献[1-2]提出了点可区别边染色(也称为强边染色).文献[3]提出了图的邻强边染色(邻点可区别边染色),并得到了圈㊁完全图等某些特殊图类的邻强边色数(即邻边可区别边色数).文献[4]提出了邻点可区别全染色,引起了国内外学者的关注,得到了一些结果(参见文献[6-7,11]).文献[8]提出了图的邻点可区别I 全染色.本文根据冠图C m ㊃S n 和C m ㊃P n 的结构性质,讨论了C m ㊃S n 和C m ㊃P n 的邻点可区别I 全染色,得到了相应的色数,并给出了具体的染色方案.定义1[8] 若对简单连通图G (V ,E ),存在正整数k 和映射f :V (G )ɣE (G ң){1,2, ,k },使得(1)∀u v ɪE (G ),u ʂv ,有f (u )ʂf (v );(2)∀u v ,u w ɪE (G ),v ʂw ,有f (u v )ʂf (u w );(3)∀u v ɪE (G ),有C (u )ʂC (v ).则称f 是图G 的邻点可区别I 全染色,而称χia t (G )=m i n {k |G 存在一个使用k 种颜色的邻点可区别I 全染色}为G 的邻点可区别I 全色数(简记为k -A V D I T 染色),其中色集合C (u )为C (u )={f (u )}ɣ{f (u v )|u v ɪE (G )} 引理1[8]对简单连通图G (V ,E ),用Δ表示图的最大度.若∀u v ɪE (G ),有d (u )=d (v )=Δ,则有χia t (G )ȡΔ+1.定义2 S n 表示阶为n +1的星,用C m ㊃S n 表示m 个S n 的星心连成的圈,称为m 个S n (星)的心联图,或称为圈和星的冠图.设m 个S n 的星心为{v i 0|i =1,2, ,m },其余点为{v i j |i =1,2, ,m ;j =1,2, ,n },则V (C m ㊃S n )={v i 0|i =1,2, ,m }ɣ{v i j |i =1,2, ,m ;j =1,2, ,n }①收稿日期:20110603基金项目:陕西省教育厅自然科学基金资助项目(11J K 0508).作者简介:田京京(1979),女,陕西汉中人,讲师,主要从事图论及其应用的研究.Copyright ©博看网. All Rights Reserved.E (C m ㊃S n )={v i 0v i j |i =1,2, ,m ;j =1,2, ,n }ɣ{v i 0v (i +1)0|i =1,2, ,m -1}ɣ{v m 0v 10}.定义3 若图G (V ,E )满足V (C m ㊃P n )={v i j |i =1,2, ,m ;j =0,1,2, ,n -1}E (C m ㊃P n )={v i j v i (j+1)|i =1,2, ,m ;j =0,1,2, ,n -2}ɣ{v i 0v (i +1)0|i =1,2, ,m -1}ɣ{v m 0v 10}则称C m ㊃P n 为圈和路的冠图.本文给出C m ㊃S n 和C m ㊃P n 的邻点可区别I 全色数.文中未加说明的术语㊁记号可参见文献[12].定理1 当m ȡ3,n ȡ2时,有x ia t (C m ㊃S n )=n +3.证 分3种情况考虑:情况1 当m =3时,我们只需给出C m ㊃S n 的一个n +3AV D I T 染色,为此令f 为:f (v 10)=1 f (v 20)=2 f (v 30)=3f (v 10v 20)=2 f (v 20v 30)=3 f (v 30v 10)=1f (v 10v 1j )=f (v 1j )=j +3 j =1,2, ,n f (v 20v 2j )=f (v 2j )=j +3 j =1,2, ,n f (v 30v 3j )=f (v 3j )=j +3 j =1,2, ,n 则C (v i j )={j +3|j =1,2, ,n }(i =1,2,3),且C (v i 0)={1,2,j +3} i =1{2,3,j +3} i =2{1,3,j +3} i =ìîíïïïï3故f 是C m ㊃S n 的一个n +3A V D I T 染色.情况2 当m ȡ4,m ʉ0(m o d 2)时,由引理1知,为证结论成立只需给出C m ㊃S n 的一个n +3A V D I T 染色,为此令f 为:f (v i 0)=2 i ʉ0(m o d 2)1 i ʉ1(m o d 2{) i =1,2, ,mf (v i j )=f (v i 0v i j )=j +3(i =1,2, ,m ;j =1,2, ,n );对边v 10v 20,v 20v 30, ,v m 0v 10用颜色2,3循环去染.则C (v i j )={j +3|j =1,2, ,n }(i =1,2, ,m ),且C (v i 0)={2,3,j +3} i ʉ0(m o d 2){1,2,3,j +3} i ʉ1(m o d 2{) i =1,2, ,m故f 是C m ㊃S n 的一个n +3AV D I T 染色.情况3 当m ȡ5,m ʉ1(m o d 2)时,只需给出C m ㊃S n 的一个n +3AV D I T 染色,为此令f 为:先对点v 10,v 20 ,v m 0用颜色1,2循环染;对边v 10v 20,v 20v 30, ,v m 0v 10用颜色2,3循环去染;然后将点v m 0所染颜色改为n +3,边v m 0v 10所染颜色改为1,f (v 1j )=f (v 10v 1j )=j +2 j =1,2, ,n f (v i j )=f (v i 0v i j )=j +3 i =2, ,m ;j =1,2, ,n 则C (v i 0)={2,3,j +3} i ʉ0(m o d2){1,2,3,j +3} i ʉ1(m o d2{) i =2,3, ,m -1;j =1,2, ,n C (v 10)={1,2,j +2,n +3} C (v m 0)={1,3,j +3} j =1,2, ,n 故f 是C m ㊃S n 的一个n +3AV D I T 染色.综上所述,定理1成立.定理2 当m ȡ3,n ȡ2时,有x ia t (C m ㊃P n )=4.证 分3种情况考虑:82西南师范大学学报(自然科学版) h t t p ://x b b jb .s w u .c n 第38卷Copyright ©博看网. All Rights Reserved.情况1 当m =3时,只需给出C m ㊃P n 的一个4A V D I T 染色,为此令f 为:f (v 10)=1 f (v 20)=2 f (v 30)=3f (v 10v 20)=4 f (v 20v 30)=3 f (v 30v 10)=1 对点v i 1,v i 2, ,v i (n -1)(i =1,3)用颜色2,1循环染;对点v 21,v 22, ,v 2(n -1)用颜色1,2循环染;对边v 10v 11,v 11v 12, ,v 1(n -2)v 1(n -1)用颜色2,3循环去染;对边v 20v 21,v 21v 22, ,v 2(n -2)v 2(n -1)用颜色1,3循环去染;对边v 31v 32, ,v 3(n -2)v 3(n -1)用颜色1,3循环去染;对边v 30v 31用颜色4去染.显然f 是C m ㊃P n 的一个4A V D I T 染色.情况2 当m ȡ4,m ʉ0(m o d 2)时,只需给出C m ㊃S n 的一个4AV D I T 染色,为此令f 为:f (v i 0)=2 i ʉ0(m o d 2)1 i ʉ1(m o d 2{) i =1,2, ,m对边v 10v 20,v 20v 30, ,v m 0v 10用颜色2,3循环去染;对点v i 1,v i 2, ,v i (n -1)(i ʉ1(m o d 2))用颜色2,1循环染;对点v i 1,v i 2, ,v i (n -1)(i ʉ0(m o d 2))用颜色1,2循环染;对边v i 0v i 1,v i 1v i 2, ,v i (n -2)v i (n -1)(i ʉ1(m o d 2))用颜色1,3循环去染;对边v i 1v i 2,v i 2v i 3, ,v i (n -2)v i (n -1)(i ʉ0(m o d 2))用颜色3,1循环去染;对边v i 0v i 1(i ʉ0(m o d 2))用颜色4去染.则C (v i 0)={2,3,4} i ʉ0(m o d 2){1,2,3} i ʉ1(m o d 2{) i =1,2, ,mC (v i 1)={1,3,4} i =0(m o d 2)C (v i j )={1,2,3} j ʉ0(m o d 2){1,3} j ʉ1(m o d2{) i ʉ0(m o d 2);j =2,3, ,n -2C (v i j )={1,3} j ʉ0(m o d2){1,2,3} j ʉ1(mo d 2{) i ʉ1(m o d 2)故f 是C m ㊃P n 的一个4A V D I T 染色.情况3 当m ȡ5,m ʉ1(m o d 2)时,证明过程与定理2的情况2类似.综上所述,定理2得证.参考文献:[1]B U R R I S A C ,S C H E L P R H.V e r t e x -D i s t i n g u i s h i n g P r o p e rE d g e -C o l o r i n g [J ].Jo fG r a p h T h e o r y ,1997,26(2):73-82.[2] B A Z G A N C ,HA R K A T -B E N HAM D I N E A ,L IH a o ,e t a l .O nt h eV e r t e x -D i s t i n g u i s h i n g P r o p e rE d g e -C o l o r i n g [J ].C o m b i nT h e o r y:S e rB ,1999,75(2):288-301.[3] Z HA N GZ h o n g -f u ,L I U L i n -z h o n g ,WA N G j i a n -f a n g .A d j a c e n t S t r o n g E d g eC l o r i n g o fG r a p h [J ].A p p l i e d M a t h e m a t -i c sL e t t e r s ,2002,15(5):623-626.[4] Z HA N GZ h o n g -f u ,C H E N X i a n g e n ,L I J i n g -w e n ,e t a l .O nA 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 g T o t a lC o l o r i n g o fG r a p h s [J ].S c i e n c e i nC h i n a :S e rA ,2005,48(3):289-299.[5] 张忠辅,李敬文,陈祥恩,等.图的距离不大于β的任意两点可区别边染色[J ].数学学报,2006,49(3):703-708.[6] WA N G H a i -y i n g .O nt h eA d j a c e n tV e r t e xD 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 f t h eG r a p h sw i t h Δ=3[J ].J 92第2期 田京京:冠图C m ㊃S n 和C m ㊃P n 的邻点可区别I 全色数Copyright ©博看网. All Rights Reserved.03西南师范大学学报(自然科学版)h t t p://x b b j b.s w u.c n第38卷C o m b i nO p t i m,2007,14:87-109.[7]J O N A T HA N H.C o n c i s eP r o o f s f o rA 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 g s[J].D i s c r e t eM a t h e m a t i c s,2009,309(8):2548-2550.[8] Z HA N G Z h o n g-f u,WO O D A L L D R,L I J i n g-w e n,e t a l.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 I-T o t a lC o l o r i n g o fG r a p h s[D].兰州:兰州交通大学,2008.[9]田京京,邓方安,张忠辅.C m㊃S n的D(2)点可区别边色数[J].数学的实践与认识,2008,38(16):149-153.[10]李敬文,王鸿杰,文飞,等.图K_(2n)\E(K_(1,m))(nȡ2)的点可区别边染色[J].西南大学学报:自然科学版,2012,34(8):86-90.[11]孙磊,孙艳丽,董海燕.几类图的相邻顶点可区别的全染色[J].西南师范大学学报:自然科学版,2006,31(4):1-4.[12]B O N D YJA,MU R T Y USR.G r a p hT h e o r y w i t hA p p l i c a t i o n[M].N e w-Y o r k:T h eM a c m i l l a nP r e s sL t d,1976.O nA 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 I-T o t a l C h r o m a t i cN u m b e ro f t h eC r o w nG r a p h C m㊃S n a n d C m㊃P nT I A NJ i n g-j i n gD e p a r t m e n t o fM a t h e m a t i c s,S h a n n x i U n i v e r s i t y o f T e c h n o l o g y,H a n z h o n g S h a n n x i723000,C h i n aA b s t r a c t:I n t h i s p a p e r,a c c o r d i n g t o t h e p r o p e r t i e s o f t h e c r o w n g r a p h C m㊃S n a n d C m㊃P n,t h e a d j a c e n t v e r t e xd i s t i n g u i s h i n g I-t o t a l c o l o r i n g o f t w ok i n d s o f c r o w n g r a p h C m㊃S n a n d C m㊃P n h a v e b e e nd i s c u s s e d b y m e a n s o f c o l o r o n e b y o n e a n d r e c u r s i o n.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 i n g I-t o t a l c h r o m a t i c n u m b e r o f C m㊃S n a n d C m㊃P n h a v eb e e no b t a i n e d,a n d t h e c o l o r i n g m e t h o do f t h e c r o w n g r a p h C m㊃S n a n d C m㊃P n h a v eb e e n g i v e n.K e y w o r d s:g r a p h;s t a r;p a t h;c r o w n g r a p h;a d j a c e n t v e r t e xd i s t i n g u i s h i n g I-t o t a l c o l o r i n g;a d j a c e n t v e r-t e xd i s t i n g u i s h i n g I-t o t a l c h r o m a t i c n u m b e r责任编辑廖坤Copyright©博看网. All Rights Reserved.。

Mycielski图的一般邻点可区别全色数王继顺【摘要】设图G(V,E)是阶数至少为2的简单连通图,k是正整数.从VUE到{1,2,…,k}的映射f称为图G的一般邻点可区别全染色(简记k-GAVDTC),如果对任意2个相邻顶点u≠v的色集合C(u)≠C(v),其中C(u)={f(u)}U{f(uv)| uv∈E(G)},并称χgat(G)=min{k| G有k-GAVDTC}为图G一般邻点可区别全色数.综合运用构造法、调整法及概率法讨论了路、圈、扇、星、轮和完全二部图的Mycielski图的一般邻点可区别全染色,给出了其确切的一般邻点可区别全色数.%In the report,let G(V,E) be a simple connect graph with order at least 2 and k be a positive integer.Mappingffrom V U E to { 1,2,…,k } was named a general a djacent vertex distinguishing total coloring of G,or k-GAVDTC,if (V)uv ∈E(G),C（u) ≠ C(v),in which C(u) ={f(u) } U {f(uv) | uv∈E(G)}.The number χgut (G)=min{ k | k-GAVDTC of G } is named the general adjacent vertex distinguishing total chromatic number of G.The combination of structural method,adjustment method and probability method,were used to discuss the general adjacent vertex distinguishing total coloring of Mycielski graphs of some particular graphs such as path,cycle,fan,star,wheel and complete bipartite graph.And the general adjacent vertex distinguishing total chromatic number of them was confirmed.【期刊名称】《海南大学学报（自然科学版）》【年(卷),期】2016(034)004【总页数】6页(P307-312)【关键词】Mycielski图;一般邻点可区别全染色;一般邻点可区别全色数【作者】王继顺【作者单位】连云港师范高等专科学校数学与信息工程学院,江苏连云港222006【正文语种】中文【中图分类】O157.5由信息科学中的电信通讯站的频率分配问题、计算机科学中的网络结构设计区分问题所引出的点可区别边染色[1-3]，邻点可区别边染色[4-5]，邻点可区别全染色[6]等具有一定的理论价值和实际意义，逐渐成为图论工作者研究的重要课题[7-10].为拓展图染色理论的应用领域，文献[11]进一步提出了一般邻点可区别边染色概念，文献[12-13]提出图的一般邻点可区别全染色的新染色概念. 由于其同样是十分困难的问题，至今文献甚少. 文献[14]根据路、圈、扇、轮等图的结构性质，确定了其一般邻点可区别的全色数．定义1[6] 设G(V，E)是简单连通图，k是正整数，f是V∪E(G)到{1，2，…k}的映射，若f满足1) 对任意uv,uw E(G), v≠w，有f(uv)≠f(uw);2) 对任意uvE(G), 有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的k-正常全染色，进一步；3) 对任意uvE(G),有C(u)≠C(v)，则称f为G的一个k-邻点可区别全染色法(简记为k-AVDTC)，而称χat(G)=min{k|G的k-AVDTC}为G的邻点可区别全色数，其中C(u)={f(u)|uV(G)}∪{f(uv)|uvE(G)}称为点u在f下的色集.定义2[12-13] 设G(V,E)是简单连通图，k是正整数，f是V(G)∪E(G)到{1，2，…k}的映射，若对任意uvE(G)，有C(u≠)C(v)，则称f为G的一般邻点可区别全染色(简记为k-GAVDTC)，并称χgat(G)=min{k|G有k-GAVDTC}为G的一般邻点可区别全色数.关于图的一般邻点可区别全色数，有2个猜想.猜想1[12-13] 设G(V，E)是有n个顶点的简单图，有⎤+1.猜想2[12-13] 设G(V，E)是有n个顶点的简单图，且Δ(G)≥4，则χgat≤Δ(G)+1.定义3[15-16] 设G(V，E)是简单连通图，若图M(G)满足V(M(G))=V∪V′∪{ω}，E(M(G))=E(G)∪{uv′|uV，v′V′，uvE(G)}∪{ωv′|v′V′}，其中，V′={v′|vV}，{ω}∩V∩V′=Ø，则称M(G)为由G构造而得的Mycielski图.Mycielski图是图论中一种重要的图，也是实际应用中经常遇到的一种网络.文献[7,15-17]研究了Mycielski图的相关染色，笔者从Mycielski图的构造特点出发，运用构造法、概率法及色调整技术研究了路、圈、扇、星、轮、完全图和完全二部图的一般邻点可区别全染色问题，得到其一般邻点可区别全色数.文中所涉及的图都是简单连通有限图，未给出的术语与记号参见文献[18].引理1 设G(V，E)图为简单图，1) 如果E(G)≠Ø，则χgat(G)≥2；2) 如果G(V,E)含K3，则χgat(G)≥3.引理2 如果G(V，E)含C5，则χgat(G)≥3.证明不然，根据引理1 1),χgat(G)≥2.假设χgat(G)=2, 不是一般性，对于G(V，E)首先染其C5.事实上，令C5=v1v2v3v4v5v1且C(v1)={1}，则f(v2)=1,f(v2v3)=2，或f(v2)=2,f(v2v3)=1,或f(v2)=2,f(v2v3)=2，而f(v3)=2,f(v3v4)=2，或f(v3)=1,f(v3v4)=1根据如此染色，有定理1 设Pn为n(n≥2)阶路，则证明设Pn=v1v2…vn，分2种情况进行证明.情形1 当n=2,注意到M(Pn)=C5，由引理2，χgat(M(Pn))=3[12-13].情形2 当n≥3，根据引理2，χgat(M(Pn))≥3. 为证χgat(M(Pn))=3，构造映射f：V∪E(M(Pn)){1，2，3}如下定理2 设Cn是n(n≥3)阶圈，则证明设Cn=v1v2…vnv1，分3种情况进行讨论.情形1 当n=3时，M(C3)包含有K3, 按照引理1 2), 有χgat(M(C3))≥3.为证结论成立, 只需给出M(C3)的一个3-GAVDTC. 令f，,n.易于验证f是M(C3)的一个3-GAVDTC. 所以χgat(M(Pn))=3.情形2 当n≥4时, 根据引理2, 有χgat(M(Pn))≥3. 现在只需构造M(C3)的一个3-GAVDTC法f. 为此，从2个方面考虑.情形(1) 当n≡0(mod 2)时, 令f易见，f为M(Cn)的一个3-GAVDTC(n≡0(mod 2)). 所以结论成立.情形(2) 当n≡1(mod 2)时,令f显然,f是M(Cn)的一个3-GAVDTC(n≡1(mod 2)).所以结论成立.定理3 设Fn是有n+1(n≥2) 个顶点的扇, 则证明根据引理1 2), χgat(M(Fn))≥3. 只需构造M(Cn)的一个3-GAVDTC. 令d(v0)=n, v0V(Fn),Fn的其他顶点分别为v1,v2,v3,…,vn.令f显然, f为M(Fn)的3-GAVDTC. 从而结论成立.定理4 设Wn是有n+1(n≥3)个顶点的轮,则证明令d(v0)=n,v0V(Wn),其他顶点分别为v1,v2,v3,…,vn,从2个方面考虑.情形1 当n≡0(mod 2)时, 根据引理1 2),χgat(M(Wn))≥3. 为证结论成立, 只需构造M(Wn)的一个3-GAVDTC. 令f显然，f是M(Wn)的3-GAVDTC. 从而结论成立.情形 2 当n≡1(mod 2)时, χgat(M(Wn))≥4. 否则, 根据引理1 2),χgat(M(Wn))≥3. 令χgat(M(Wn))=3, 则所有顶点的色集必是{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}其中之一. 对于M(Wn)的轮Wn，不失一般性，首先固定顶点v0的色集为C(v0)={1}，由于每个vi都与v0相邻，所以顶点vi(i=1, 2,…,n)的色集必是{1, 2}, {1, 3}和{1, 2, 3}其中之一. 由所有的顶点组成圈Cn，且n是奇数，所以所有的顶点vi(i=1, 2,…,n)的色集含有{1, 2}, {1, 3}和{1, 2, 3},且这些色集是不能有重复色集相邻的按序排列下来.不妨令C(v1)={1,3},C(v2)={1, 2},C(vn)={1, 2, 3},则顶点vn-1的色集必然是C(vn-1)={1,2}或C(vn-1)={1,3}.下面确定的色集.当C(v1)={1,3}，C(v2)={1,2},C(vn-1)={1,2},C(vn)={1,2,3}时, 因为每个也都与v0相邻，(i=1, 2,…,n)的色集就不可能是{1}, {2}, {3} 或 {2, 3}, 而只能是{1, 2}, {1, 3}和{1, 2, 3}其中之一.与v2，vn相邻，可以确定的色集是{1, 3},同样，的色集是和即可能是{1, 2}或{1, 3}.由于与所有的vi(i=1, 2,…,n)相邻，可以确定的色集是{1}或{2, 3}.考虑的所有可能情况, 所有色集{1}, {2}, {3}; {1, 2}, {1, 3}, {2, 3} 和 {1, 2, 3}都不可能确定为ω的色集.当C(v1)={1, 3},C(v2)={1, 2},C(vn-1)={1, 3},C(vn)={1, 2, 3}时，情况也是如此. 为此假定C(v0)={1}不可能. 对于其他情况如C(v0)={1,2},C(v0)={1, 2, 3},同样推得不可能. 所以当n≡1(mod 2)时，χgat(M(Wn))≥4.为证χgat(M(Wn))=4，构造M(Wn)(n≡1(mod 2))的4-GAVDTC法f则显然,f是M(Wn)的4-GAVDTC(n≡1(mod 2)).从而结论成立.定理5 设完全二部图为Km,n, 则证明令(X,Y)为Km,n的二部顶点集对. 根据引理2, χgat(M(Km,n))≥3.首先, 用色1, 2和3染M(Km,n)的顶点集X和X′的所有顶点，用色1染所有的边，然后用色2染顶点集Y和Y′的所有顶点，最后用色3染顶点ω. 显然该f是M(Km,n)的3-GAVDTC. 结论成立.推论1 设Sn=K1,n是有n+1(n≥2)个顶点的星, 则证明根据定理5，结论显然.由上述结论，关于Mycielski图的一般邻点可区别全色数，可得定理6.定理6 设G(V,E)为任意简单图, 则证明按照定义1, 显然有χgat(M(G))≥χgat(G). 仅需证明χgat(M(G))≤χgat(G)+1.令H=M(G)=G，再让H=Sn，其中Sn为阶是n=|V(G)|. 现在以χgat(M(G))色(令k)染G，用色k+1染图H(d(H)=n)的顶点，用色1染H=Sn的边；对任意uG, 以G中染u的关联边的色来染边uv(vH)，且当uG，v′H，uvE(G)时，对任意v′H(dv′(H)=1)用与顶点u相同的色来染. 由此可以验证结论成立.。

目录中文摘要------------------------------------------------------------------2 英文摘要------------------------------------------------------------------3 引言----------------------------------------------------------------------4 一、mycielski图的定义-----------------------------------------------------5 1． mycielski图的定义----------------------------------------------------52 . 广义mycielski图的定义-----------------------------------------------5二、mycielski图的染色问题-------------------------------------------------5(一)边色数----------------------------------------------------------------51. Mycielski图的边色数---------------------------------------------------52.广义Myc ielski 图的边色数----------------------------------------------6(二)邻强边色数------------------------------------------------------------61. Myciel ski 图的邻强边色数---------------------------------------------72. 广义Mycielski 图的邻强边色数------------------------------------------7 （三）全色数--------------------------------------------------------------81. Mycielski图的全色数--------------------------------------------------82. 广义Mycielski图的全色数---------------------------------------------9 （四）邻点可区别全色数----------------------------------------------------91.Mycielski 图的邻点可区别全色数---------------------------------------102.广义Mycielski图的邻点可区别全色数----------------------------------12 致谢--------------------------------------------------------------------13 参考文献----------------------------------------------------------------14Mycielski图的染色问题摘要：本论文总结了Mycielski 图及广义Mycielski 图关于染色问题的各方面定义和定理，主要包括边色数、邻强边色数、全色数、邻点可区别全色数的相关结论。

关于几类特殊图的Mycielski图的邻点可区别全色数陈祥恩;张忠辅;晏静之;张贵仓【期刊名称】《兰州大学学报（自然科学版）》【年(卷),期】2005(041)002【摘要】设G是一个简单图,f是一个从V(G)∪ E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是G的正常全染色且u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设xat(G)=min{k|G存在k-AVDTC},则称xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数.%Let G be a simple graph, f be a mapping from V(G) U E(G) to {1, 2, … , k}. Let Cf(v) = {f(v)}∪{f(vw)|w ∈ V(G), vw ∈ E(G)}for every v ∈ V(G). Iff is a k-proper-total-coloring, and for u, v ∈ V(G), uv ∈ E(G), we have Cf(u) ≠ Cf(v), then f is called the k-adjacent-vertex-distinguishing total coloring(k-AVDTC for short). Let xat(G) = min{k|G has a k-adjacent-vertex- distinguishing total coloring}. Then xat(G) is called the adjacent-vertex-distinguishing total chromatic number. The adjacent-vertex-distinguishing total chromatic numbers on Mycielski's graphs of path, cycle, complete graph, complete bipartite graph, star, fan and wheel are presented in this paper.【总页数】6页(P117-122)【作者】陈祥恩;张忠辅;晏静之;张贵仓【作者单位】西北师范大学,数学与信息科学学院,甘肃,兰州,730070;西北师范大学,数学与信息科学学院,甘肃,兰州,730070;兰州交通大学,应用数学研究所,甘肃,兰州,730070;兰州大学,数学与统计学院,甘肃,兰州,730000;西北师范大学,数学与信息科学学院,甘肃,兰州,730070【正文语种】中文【中图分类】O1【相关文献】1.两类特殊的k重Mycielski图的邻点强可区别E-全染色 [J], 李雨虹;强会英;顾忠栋2.若干图广义Mycielski图的点边邻点可区别的全染色 [J], 强会英;张忠辅3.关于几类特殊图的Mycielski图的点可区别全色数 [J], 安明强;刘信生;陈祥恩4.P2n的Mycielski图的邻强边色数和邻点可区别全色数 [J], 孔令峰;苏文龙;罗海鹏;黎贞崇;何建东5.广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界 [J], 李沐春;强会英;张忠辅因版权原因，仅展示原文概要，查看原文内容请购买。

几类图的2-距离和可区别染色几类图的2-距离和可区别染色简介：图论是研究顶点和边构成的图的结构和性质的数学学科。

其中，图的距离和染色是图论中的两个重要概念。

本文将讨论几类特殊的图的2-距离和可区别染色，并探讨它们的性质和应用。

一、路径图的2-距离和可区别染色路径图是由一系列不相交的边连接的顶点构成的图，顶点按顺序排列，边只能连接相邻的两个顶点。

对于路径图，我们可以定义2-距离为两个顶点之间的距离。

例如，路径图中相邻顶点的距离为1，隔一个顶点的距离为2，以此类推。

而在路径图的可区别染色中，相邻的两个顶点不能染成相同的颜色。

通过对路径图的研究，我们可以发现以下性质：1. 路径图的2-距离是唯一确定的，两个不同的顶点之间的2-距离不同。

2. 路径图的可区别染色需要至少n种颜色，其中n是顶点的个数。

3. 路径图是可完全染色的，即可以使用n种颜色将路径图的顶点染色，且相邻的两个顶点颜色不同。

二、环图的2-距离和可区别染色环图是由一系列相邻的顶点构成的图，首尾相连形成一个循环。

对于环图，我们同样可以定义2-距离为两个顶点之间的距离。

而在环图的可区别染色中，相邻的两个顶点不能染成相同的颜色。

与路径图不同的是，环图的性质有所差异：1. 环图的2-距离是多样的，同一个顶点到不同顶点的2-距离可相同。

2. 环图的可区别染色需要至少2种颜色，即使顶点个数增加，所需的颜色数目也不变。

3. 环图是可完全染色的，可以使用2种颜色将环图的顶点染色，其中相邻的两个顶点颜色不同。

三、完全图的2-距离和可区别染色完全图是每两个顶点之间都存在边的图。

对于完全图，我们同样可以定义2-距离为两个顶点之间的距离。

而在完全图的可区别染色中，相邻的两个顶点不能染成相同的颜色。

完全图的性质如下：1. 完全图的2-距离是唯一确定的，两个不同的顶点之间的2-距离不同。

2. 完全图的可区别染色需要至少n种颜色，其中n是顶点的个数。

3. 完全图是可完全染色的，可以使用n种颜色将完全图的顶点染色，其中相邻的两个顶点颜色不同。