Wm∨C4的点可区别正常边色数

图的色数与其补图边色数的关系
关于图的色数与其补图边色数的关系，将不失为一个相当有趣而又重要的课题。

据统计，有关图的色数与其补图边色数问题近年来已经引起了许多学者、专家以及商业市场研究者的关注，使人们受益良多。

图的色数，以及其补图边色数的变化，是指当图被给定基础颜色时，其补图边
的颜色数发生的变化。

由于不同的绘图技术，究其原因可能有很多。

在讨论图的色数与其补图边色数之前，首先要明确图和其补图边之间的关系。

图和其补图边是一种相对表达关系。

它们可以划分为两个部分，即图和它的补
图边。

图由连接图节点的边构成，而补图边则是将所有节点连接起来的边。

它们之间的关系，是“每一条补图边都需要使用一种图色，以便将图着色”，而没有存在多余的图色。

因此，在研究图的色数与其补图边色数时，首先要明确图和其补图边之间的关系，并确定每一种颜色在图和其补图边之间的影响。

根据不同的绘图技术，研究者们经常利用各种算法、方法，尤其是基于排序的算法来优化着色结果，以最少的图色即可着色图的全部节点。

换句话说，当采用一种恰当的算法时，有关图的色数与其补图边色数的变化就
得以较容易地控制，从而使得着色的效果得到极大的提升。

比如，采用最小着色问题的贪心算法，人们可以较容易地求解出给定图中补图边最少要使用多少种不同颜色，从而实现有效的着色。

总之，图的色数与其补图边色数是一个相当重要的问题，研究发现，采用恰当
的算法以及着色技术，可以极大的提高给定图的着色效果，使着色效果变得更优秀、更准确、更高效。

因此，在实际应用中，运用图的色数与其补图边色数研究当中取得的成果是十分重要的。

图的直积与半强积的邻点可区别边染色索郎王青;杨青;田双亮【摘要】研究了图的直积与半强积的邻点可区别边染色,得到了直积与半强积的邻点可区别边染色数的上界,证明了染色数的上界是可达的.最后给出轮、扇与星构成的任意序列对应的直积与半强积的邻点可区别边染色数的精确值.【期刊名称】《湖北民族学院学报（自然科学版）》【年(卷),期】2018(036)003【总页数】4页(P277-280)【关键词】直积;半强积;邻点可区别边染色;邻点可区别边色数【作者】索郎王青;杨青;田双亮【作者单位】西北民族大学数学与计算机科学学院,兰州730030;西北民族大学数学与计算机科学学院,兰州730030;西北民族大学数学与计算机科学学院,兰州730030【正文语种】中文【中图分类】O157.5张忠辅等人于2002年引入了图的邻点可区别边染色概念.所谓图G的邻点可区别边染色是指G的满足任意相邻两点色集不同的正常边染色.张忠辅等人在文献[1]中研究了完全图、圈、轮、扇、树和完全偶图等特殊图的邻点可区别边染色，在此基础上，提出了有关邻点可区别边色数的猜想：阶至少为3的连通图G(G≠C5)的邻点可区别边色数不超过Δ(G)+2，其中Δ(G)表示图G的最大度.关于图的邻点可区别边染色，文献[2]给出了图的邻点可区别边色数的上界.关于运算图的邻点可区别边染色，文献[3-7]研究了特殊图的联图、特殊完全图、网格图、特殊图的笛卡尔积、超立方体等图的邻点可区别边染色.本文主要研究图的直积与半强积的邻点可区别边染色.文中所考虑的图G都是有限无向的简单连通图，用V(G)与E(G)分别表示图G的顶点集和边集.文中未加说明的术语及记号可参见文献[8-10].图G的k-正常边染色[3]σ是用k种颜色对G的边进行染色，使得相邻边染不同的颜色，最小的k值称为G的边色数，记为χa′(G).由Vizing定理可知，对任意简单图或若则称G为第一类图；若则称G为第二类图.1 预备知识在正常边染色的定义中，用Sσ(v)表示在染色σ下顶点v的关联边的颜色构成的集合.在文献[1]中,张忠辅等通过增加约束条件提出了如下特殊边染色的概念：定义1[1] 设σ为阶至少为3的简单图G的k-正常边染色,若对任意两个相邻的顶点u,v∈V(G),有Sσ(u)≠Sσ(v),则称σ为G的邻点可区别边染色或邻强边染色,且最小的k值称为G的邻点可区别边染色数,记为引理1 对阶至少为3的简单图G,若G存在相邻的最大度点,则定义2[11] G和H的直积是指具有顶点集V(G)×V(H)的图G×H，其中两个顶点(u1,v1)与(u2,v2)相邻当且仅当u1u2∈E(G)且v1v2∈E(H).由图的直积定义，显然，Δ(G×H)=Δ(G)Δ(H)，G×H≅H×G.定义3[12] 简单图G与H的半强积G·H是具有顶点集V(G)×V(H)的简单图，其中两个顶点(u1,v1)与(u2,v2)相邻当且仅当u1u2∈E(G)且v1v2∈E(H)，或u1=u2且v1v2∈E(H).根据定义3，若G为2阶完全图，即G=K2，则K2·H为H倍图[13]D[H]；若G为n≥2阶完全图，即G=Kn，则Kn·H为H的n-倍图[14]Dn[H].两个图G与H的半强积包括两个图G·H与H·G,一般而言它们是不同构的.如C4与S5两个半强积C4·S5与S5·C4是不同构的，因为S5·C4中没有3度点,而C4·S5中有3度点.设G与H是分别具有顶点集V(G)={t0,t1,…,tn-1}与V(H)={y0,y1,…,ym-1}的两个简单图,其中n≥2,m≥3.在G·H中,记vij=(ti,yj).由定义3可知,顶点集Vi={vi0,vi1,…,vi,m-1}在G·H中的导出子图与H同构,称它为H的拷贝,记为Hi，其中i=0,1,…,n-1.同时，在G中，若titj∈E(G)，则两个顶点集Vi与Vj之间的边在G·H中的导出子图是一个最大度为Δ(H)的二部图，将这个二部图记为Gij.根据半强积的定义，可将G·H分解为若干个边不交的图之并，即在下文中要用到以下引理：引理2[3] 设G是二部图，则有χ′(G)=Δ(G).引理3[1] 对n≥3阶的树T,若T中存在相邻的最大度点，则否则引理4[1] 对n≥3阶完全图Kn，若n为奇数，则否则在引理4中，当n为偶数时，Kn存在一个(n+1)-邻点可区别边染色，使得某一种颜色在Kn的每一顶点上表现，具体染色如下：设Kn的顶点集为V(Kn)=v1,v2,…,vn，颜色集合为{0,1,…,n}.令:σ(vivj)=(i+j)mod(n+1)，i≠j, i,j=1,2,…,n-1；σ(vivn)=2i mod(n+1)，i=1,2,…,n-1.由σ定义可知，未在顶点vi上表现的颜色构成的集合为{i-1,i}，其中i=1,2,…,n-1；未在顶点vn上表现的颜色构成的集合为{n-1,0}，且颜色n在Kn的每一顶点上表现.引理5[9] 对任意整数n≥3，Kn,n存在一个n-边染色，使得Kn,n有一个匹配的边染n种不同的颜色.2 主要结果及其证明定理1 设G和H为阶至少为3的简单连通图，则证明仅需证明G×H存在邻点可区别边染色.设G*是具有顶点集{V1,V2,…,Vn}(每一个Vi被视为顶点)且同构于G的图.因G*可用种颜色进行邻点可区别边染色,染色记为σ0，其中G*的各色类分别标记为A1,A2,…,Aχa(G).因对G*中每一色类Ap 的每一边ViVj,顶点集合Vi∪Vj在G×H中的导出子图是一个最大度为Δ(H)的二部图，所以可用Ap={ap,1,ap,2,…,ap,Δ(H)}中的Δ(H)种颜色对色类Ap的每一边对应G×H的导出子图进行正常边染色，其中且对有Ap∩Aq=φ.因此，可用种颜色对G×H进行边染色，染色记为σ.显然，σ是G×H的一个正常边染色.现在说明σ是邻点可区别的.任取G×H中两个相邻的顶点vip与vjq，因Sσ0(ti)≠Sσ0(tj)，所以存在标号As，使得As∈Sσ0(ti)且As∉Sσ0(tj).因此，|Sσ(vip)∩As|≥1，|Sσ(vjq)∩As|=0，故Sσ(vip)≠Sσ(vjq)，即σ是邻点可区别的.定理1的上界是可达的，具体见以下推论：推论1 设G与H为阶至少为3的简单连通图，若则证明由已知与定理1可得,而Δ(G×H)=Δ(H)Δ(G),所以设G1,G2,…,Gp是由p个最大度均为Δ的n阶连通图构成的序列,用符号Gk×(Gk-1×(…×(G2×G1)…))表示Gk与Gk-1×(…×(G2×G1)…)的直积,其中k=2,3,…,p.与图序列G1,G2,…,Gp对应的直积记为Gp×(Gp-1×(…×(G2×G1)…)),关于这个直积的邻点可区别边色数，有以下结论：定理2 若则证明反复应用推论1,可证明结论成立.定理2的结果与图序列G1,G2,…,Gp的顺序无关.根据定理2,p个n阶的轮、扇与星构成的任意序列对应的直积的邻点可区别边色数为(n-1)p,其中p≥2，n≥5.定理3 设G与H为阶至少为3的简单连通图，则证明仅需证明G·H存在邻点可区别边染色.根据半强积的定义，可将G·H分解为与G(2)=G×H.因此,可分两步构造G·H的邻点可区别边染色.首先，对G(1)进行边染色.具体地，用种颜色分别对G·H中H的各拷贝进行邻点可区别边染色,使得对应H同一边的边染相同的颜色，所用的颜色构成的集合记为A.其次，对G(2)进行边染色，染色方法与定理1证明中的σ相同，其中所用颜色不同于A中的颜色，且颜色集合记为B.显然，由以上两步构成的染色是正常边染色，记为现在说明是邻点可区别的.在G·H中,对H的每一拷贝的任意相邻两点vip与viq,有又因A∩B=φ及所以即vip 与viq是可区别的.对属于H的不同拷贝的任意相邻两点vip与vjq,由定理1证明可知，所以，即vip与vjq是可区别的.因此,是邻点可区别的.定理3的上界是可达的，具体见以下定理：定理4 设G与H为阶至少为3的简单连通图.若且则特殊地，当Δ(G)=Δ(H)时，有证明由半强积的定义可知,由已知与定理因此,类似地,可证明当Δ(G)=Δ(H)时，有因此,定理结论成立.因n≥5阶的轮Wn、扇Fn与星Sn的邻点可区别边色数等于它们的最大度n-1，即由定理4，有以下结论：当G与H均为n≥5阶的轮Wn或扇Fn或星Sn时，两个不同半强积G·H与H·G的邻点可区别边色数均为n(n-1).定理5 设G是满足的n≥3阶简单连通图,H为m≥3阶完全图即H=Km,则证明显然,现在分两种情况证明:情况1 m为奇数.由引理由定理情况2 m为偶数.设G的顶点集为V(G)={t0,t1,…,tn-1}，并记Δ(G)=Δ.因所以G的最大度点均不相邻，记为t0.设颜色集为其中不同的Bi互不相交，且Bi={bi0,bi1,…,bi,m-2},i=0,1,…,Δ-1,BΔ={a0,a1,…,am-1}.与定理3证明类似，将G·H分解为与G(2)=G×H.现在分以下三步构造G·H的(Δ(m-1)+m)-邻点可区别边染色：首先，对G(2)进行边染色.因所以可将E(G)划分为Δ个匹配，并用B0,B1,…,BΔ-1分别标记，使其满足邻点可区别边染色的要求，不妨设t0t1标记为B0，该染色记为σ0.对G的邻点可区别边染色σ0，每一色类与每一边titj对应.G(2)中的子图Gij 是最大度为m-1的正则二部图，所以σ0中每一色类的每一边可用m-1个匹配代替，并得到了G(2)的一个边染色，记为σ1.其次，在G(2)的边染色σ1中，对其子图G01重新进行染色.记其中M={v0iv1i|i=0,1,…,m-1}，显然，≅Km,m.根据引理5，可用B0∪{a0}中的m种色对进行正常边染色，使得M中的各边染不同的颜色.然后，从中删去M的所有边可得到G01的一个新的边染色.G(2)的这个新的边染色记为σ2.显然，在σ2中，Vi的不同顶点是可区别的，其中i=0,1.最后，对G(1)进行边染色.因偶阶完全图是第一类的图，所以χ′(H)=m-1.因此，可用BΔ-{a0}中的m-1种颜色分别对H的两个拷贝H0与H1进行正常边染色.对任意ti∈V(G)-{t0,t1}，因dG(ti)≤Δ-1，所以在G的邻点可区别边染色σ0中，至少存在一种标号Bji不在ti上表现.因此，由引理4的说明，可用Bji∪{a1,a2}中的m+1种颜色对Hi进行邻点可区别边染色，使得颜色a1在Hi的每一顶点上表现，记G(1)的这一染色为σ3.将σ2与σ3合并得到G·H的边染色，记为σ.显然，σ是G·H的一个正常边染色.现在说明σ是邻点可区别的.对于G·H的任意两个相邻顶点vir与vjs，若i=j，则由σ的定义，Sσ(vir)≠Sσ(vjs).若i≠j，当dG(ti)≠dG(tj)时，vir与vjs在G·H中具有不同的度数，所以它们是可区别的；当dG(ti)=dG(tj)时，在σ0中，存在一种标号Bp，使得Bp∈Sσ0(ti)且Bp∉Sσ0(tj).根据σ的定义,则有|Sσ(vir)∩Bp|=m-1,|Sσ(vjs)∩Bp|≤m-2.所以，Sσ(vir)≠Sσ(vjs).由以上分析可知,σ是G·H的邻点可区别边染色.因此，综合以上两种情况，定理结论成立.设G1,G2,…,Gp是由p个最大度均为Δ的n阶连通图构成的序列,用符号Gk·(Gk-1·(…·(G2·G1)…))表示Gk与Gk-1·(…·(G2·G1)…)的半强积,其中k=2,3,…,p.与图序列G1,G2,…,Gp对应的半强积记为Gp·(Gp-1·(…·(G2·G1)…)),关于这个半强积的邻点可区别边色数，有以下结论：定理6 若则证明反复应用定理4，可证明结论成立.值得注意的是，定理6的结果与图序列G1,G2,…,Gp的顺序无关.根据定理6，p 个n阶的轮、扇与星构成的任意序列对应的半强积的邻点可区别边色数为np-1(n-1)，其中p≥2，n≥5.参考文献:【相关文献】[1] ZHANG Z F,LIU L Z,WANG J F.Adjacent strong edge coloring of graphs[J].Applied Mathematics Letters,2002,15(5):623-626.[2] HATAMI H.Δ+300 is a bound on the adjacent vertex distinguishing edge chromatic number[J].J Combin Theory Ser B,2005,95:246-256.[3] CHEN M,GUO X.Adjacent vertex-distinguishing edge and total chromatic numbers of hyper-cubes[J].Information Processing Letters,2009,109:599-602.[4] WANG T,ZHAO Y B,LI D M.Adjacent strong edge coloring and equitable adjacent strong edge coloring of the joins of paths[J].Journal of Anhui University (Natural Science Edition),2012,36(1):33-37.[5] AKBARI S,BIDKHORI H,NOSRATI N.r-Strong edge colorings of graphs[J].Discrete Math，2006,306:3005-3010.[6] BALISTER P N,GYORI E,LEHEL J,et al.Adjacent vertex distinguishing edge-colorings[J].SIAM J Discrete Math，2007,21:237-250.[7] TIAN S L,LI J W,MA S X.On the Adjacent Strong Edge Chromatic Number ofK(r,2)[J].Mathematics in Economics,2005,22(1):105-107.[8] BONDY J A,MURTY U S R.Graph Theory with Applications[M].New York:American Elsevier,1976.[9] YOP H P.Total Coloring of Graph[M].New York:Springer Verlag,1996.[10] REINHARD D.Graph Theory[M].New York:Springer Verlag,1997.[11] BONDY J A,MURTY U S R.Graph Theory with applications[M].NewYork:Macmillan,1976.[12] JARADAT M M M.On the edge coloring of graph products[J].International Journal of Mathematics and Mathematical Sciences,2005,16:296-301.[13] 张忠辅,仇鹏翔,张东翰，等.图的倍图与补倍图[J].数学进展,2008,37(3):303-310.[14] 郭利涛,覃城阜.n-double图的连通性[J].应用数学学报,2013,36(2):204-208.。

Sm∨Pn的邻点可区别全色数
谷玉盈;李桂玲
【期刊名称】《山东科技大学学报（自然科学版）》
【年(卷),期】2006(025)001
【摘要】设G的阶数不小于2的简单连通图.G的k-正常全染色称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同.这样的k中最小者称为G的邻点可区别全色数.本文主要是给出了星图和路的联图的邻点可区别全色数,并提出了一猜想.
【总页数】3页(P105-106,109)
【作者】谷玉盈;李桂玲
【作者单位】山东科技大学,信息科学与工程学院,山东,青岛,266510;山东科技大学,信息科学与工程学院,山东,青岛,266510
【正文语种】中文
【中图分类】O157.5
【相关文献】
1.Pn×Pm图的邻点可区别全染色和邻点强可区别全染色 [J], 张锐;刘永平;刘海涛;张效贤;谢继国
2.多重联图Sm∨Pn∨Pn的邻点可区别全色数 [J], 田京京;刘信生;张忠辅
3.冠图Cm·Sn和Cm·Pn的邻点可区别Ⅰ-全色数 [J], 田京京
4.多重联图Sm∨Pn∨Pn 的邻点可区别边色数 [J], 刘信生;田京京
5.C3m×C3n、C4m×C4n的邻点强可区别全染色及全色数 [J], 张效贤
因版权原因，仅展示原文概要，查看原文内容请购买。

关于图的点色数和邻点可区别E-全色数郑艺容;陈美润;翟绍辉【期刊名称】《海南师范大学学报（自然科学版）》【年(卷),期】2015(000)002【摘要】The chromatic number of a graphG, denoted byχ(G), is the minimum number k for which G has a proper k-vertex coloring. The adjacent vertex-distinguishing E-total chromatic number of G, denotedbyχeat (G ), is the minimum number k for which G has an adjacent vertex-distinguishing E-total coloring. These two colorings seem to be different, but we proved that χ(G )=χeat (G ) when χ(G)≥4.%图G的点色数χ（G）是指图G存在正常k-顶点着色的k的最小值，图G的邻点可区别E-全色数χeat (G )是指图G存在邻点可区别E-全染色的k的最小值。

尽管图G的这两种染色看似不同，但我们证明：当χ（G）≥4时，χ(G )=χeat (G )。

【总页数】3页(P131-133)【作者】郑艺容;陈美润;翟绍辉【作者单位】厦门理工学院应用数学学院，福建，厦门 361024; 福州大学离散数学研究中心，福建，福州 350116;厦门理工学院应用数学学院，福建，厦门361024;厦门理工学院应用数学学院，福建，厦门 361024【正文语种】中文【相关文献】1.扭立方体图的全色数和邻点可区别全色数 [J], 陈美润2.某些中间图的邻点可区别E-全色数 [J], 王继顺3.Cartesian积图的关联色数与邻点可区别关联色数 [J], 董桂香;张丽4.幂图Pkn的邻点可区别全色数和邻点可区别-VE全色数 [J], 田京京5.广义Mycielski图的邻强边色数和邻点可区别全色数的两个上界 [J], 李沐春;强会英;张忠辅因版权原因，仅展示原文概要，查看原文内容请购买。