论文部分内容阅读
在本文中，我们用[x]表示不大于实数x的最大整数，用[x]表示不小于实数x的最小整数.用|S|表示集合S中元素的个数.
除非特别指出，本文所讨论的图均为简单，有限，无向图.我们用V(G)和E(G)分别表示图G的顶点集和边集.对于任意顶点v∈V(G)，用dG(v)表示顶点v在图G中的度.用δ(G)和△(G)分别表示图G中顶点的最小度和最大度.G[V′]表示图G由顶点子集V′导出的子图，G[E′]表示图G由边子集E′导出的子图.Kn表示n个顶点的完全图.ω(G)表示图G的连通分支个数，κ(G)表示图G的连通度.α(G)表示图G的独立数，χ(G)表示图G的色数.本文所用术语与符号基本与文献[1]中一致.
随着图的染色问题在现实中被广泛应用，它逐渐成为众多学者研究的重要领域之一.在[2，3]中，起源于网络问题的点可区别边染色和邻点可区别边染色问题得到进一步研究.新的染色问题不断被提出，与该问题相关的，[4，5]中相继给出了(邻)点可区别全染色的定义及其几类简单图关于此染色的色数，并提出相关猜想.
张忠辅给出的(邻)点可区别全染色定义是这样的：设图G(V，E)为阶至少为2的简单连通图，k为正整数.函数f是从V(G)∪E(G)到C={1，2，…，k}的一个映射.
对于任意顶点u∈V(G)，记C(u)={f(u)}∪{f(uv)|uv∈E(G)}，-C(u)=C-C(u).
(1)对任意边uv，vw∈E(G)，且u≠w，有f(uv)≠f(vw).
(2)对任意边uv∈E(G)，且u≠v，有f(u)≠f(v)，f(u)≠f(uv)，f(uv)≠f(v).
(3)对于任意边uv∈E(G)，且u≠v，有C(u)≠C(v).
(4)对于任意点u，v∈V(G)，且u≠v，有C(u)≠C(v).
若满足条件(1)，(2)，则称f为图G的一个k-正常全染色(简记为k-TC).若满足条件(1)，(2)，(3)，则称f为图G的一个k-邻点可区别全染色(简记为k-AVDTC).
若满足条件(1)，(2)，(4)，则称f为图G的一个k-点可区别全染色(简记为k-VDTC).
图G的全色数为χT(G)=min{k}图G有k-TC}.图G的邻点可区别全色数为χat(G)=min{k|图G有k-AVDTC}.图G的点可区别全色数为χvt(G)=min{k|图G有k-VDTC}.
下面两个关于邻点可区别全染色的结论显然：对任意阶为n(n=|V(G)|≥2)的简单连通图G，邻点可区别全色数χat(G)存在，并且χat(G)≥△(G)+1.若图G(V，E)有两相邻的最大度顶点，则χat(G)≥△(G)+2.张忠辅在文献[4]中给出了关于邻点可区别全色数的猜想：对任意阶为n(n=|V(G)|≥2)的简单连通图G，有χat(G)≤△(G)+3.
对于路，圈，完全图，完全二部图，星，扇，轮，树等特殊图类，张忠辅在文献[4]中给出了具体的邻点可区别全色数，并且满足上述猜想.
关于点可区别全染色，张忠辅在文献[5]中给出了完全图，完全二部图，扇，轮，双星，还有一系列联图的点可区别全色数.并提出相关猜想：对任意阶为n(n=|V(G)|≥2)的简单连通图G，有KT(G)≤χvt(G)≤KT(G)+1.
其中KT(G)=max{t|t=min{kd|(Ckdd+1)≥nd}，δ(G)≤d≤△(G)}.并且，nd=nd(G)表示图G中度为d的顶点个数.
E.Scheinerman和D.Ullman在[6]中提出了分数染色的概念，它是图染色的分数推广.作者并指出：确定任意一个图的分数色数是NP-完全问题.
图G的一个分数染色是从G的独立集集合ζ到区间[0，1]的一个映射C，使得对任意顶点x，都有∑I∈ζ，s,t,x∈IC(I)≥1，将此分数染色的值定义为∑I∈ζC(I)，图G的分数色数χf(G)是它的所有分数染色值的下确界.
图G的分数色数另一个等价定义为χf(G)=limb→∞χb(G)b=infbχb(G)/b，其中χb(G)为G的b-层色数.给图G的每个顶点以一个b种颜色的色集，使得相邻两顶点的色集不交，若所有颜色均取自一个a种颜色的色集，这时，我们称图G是a：b-可染的，且称此染色为一个a：b-染色.使得图G有一个a：b-染色的最小的a，称为图G的b-层色数.即χb(G)=min{a|G有一个a：b-染色}.
在本文中，关于图的(邻)点可区别全染色，我们主要得到如下定理.具有顶点集V(G)={ui∪vj|i=1，2，…，m；j=1，2，…，n；m≥n≥2}和边集E(G)={uivj|i=1，…，m；1≤j≤i}的图，我们称之为“次完全二部图”.记作：Gm,n*.
定理2.1.1χat(Gm,n*)={m+2,m=n≥2m+1,m＞n≥2.在圈CN=v1v2…unv1的每个顶点vi上增加一条悬挂边vivi1(i=1，…，n)，得到图Yn(1)，在每个顶点vi上再增加一条悬挂边vivi2(i=1，…，n)，得到图Yn(2)，…，第k次(k可任意大)增加悬挂边vivik(i=1，…，n)，得到图Yn(k)…这样，我们得到一系列的烟花图Yn(1)，Yn(2)，…，Yn(k)…..其中图Yn(1)，为我们所熟知的王冠Qn.
定理2.1.2χat(Yn(k))=k+4(n≥3).
定理2.1.3χvt(Yn(1))=χvt(Qn)=n(n≥5).
在两圈C1=u1u2…unu1(n≥3)和C2=v1v2…vnv1(n≥3)间逐次叠加匹配uivi，uivi+1，…，uivi+k，…，uivi+(n-1)，(i=1，2，…，n；k=0，1，…，n-1；当i+k＞n+1时，i+k为modn意义下的加法)，这样可得到一系列正则图：Cn,n(1)，Cn,n(2)，…，Cn,n(k+1)，…，Cn,n(n)=Cn∨Cn.
定理2.1.4当n≥4且n≡0(mod2)时，χat(Cn,n(k+1))=△(Cn,n(k+1))+2=k+5.
定理2.1.5当n≥4且n≡1(mod2)时，(1)χat(Cn,n(1))=5.
(2)当1≤k≤n-1时，k+5≤χat(Cn,n(k+1))≤k+6.在王冠Qn(n≥3)的悬挂点ui上加边uivi-1和utivi+1(i=2，3，…，n-1)；在点u1上加边u1v2和u1vn；在点un上加边unvn-1和unv1；得到特殊王冠Qn*.
定理2.1.6χat(Qn*)=7(n≥3).
将圈Cn=v1v2…vnv1(n≥3)的每条边vivi+1(i=n时，为vnv1)以双重边(无方向)代替，对每对双重边外部的一条相应的加剖分点vi(i=1，2，…，n)，得到向日葵Hn.
定理2.1.7χat(Hn)=6(n≥3).
在向日葵Hn(n≥3)的边vivi+1(i=n时，为vnv1)上相应的加剖分点wi(i=1，2，…，n)，得到篱笆圈Pn*.
定理2.1.8χT(Pn*)=χat(Pn*)=5(n≥3).在圈C2n=v1v2…v2n-1v2nv1(n≥2)的每个顶点vi上增加悬挂边viui(i=1，2，…，2n)，再加边uiui+1(i≡1(mod2))，得到风车W2n*.
定理2.1.9χat(W2n*)=5(n≥2).在本文中，关于图的分数染色，我们主要得到如下结果：给定正整数a，b，且a≥2b，图Ga,b是如下定义的[6]:其顶点集V(Ga,b)={v0，v1，…，va-1}；顶点vi的邻点为{vi+b，vi+b+1，…，vi+a+b}，其中加法是moda的.
图G称为顶点可迁图[6]：对任意顶点u，v∈V(G)，存在G的自同构射π，使得π(u)=v.
性质2.2.1[6]χf(Ga，b)=a/b；χb(Ga,b)=a.
性质2.2.2[6]对任意图G，有χf(G)≥v(G)/a(G)；进一步，当G是顶点可迁图时，等号成立.
引理2.2.3对任意顶点v∈V(Ga,b)，有a-1/b≤χf(Ga,b-v)≤a/b.
定理2.2.4当a=kb时，k∈Z且k≥2，有χf(Ga,b-v)=a/b.
定理2.2.5当a=2b+1时，χf(Ga，b-v)=a-1/b.
在图Ga，b中，令ei=(vi，vi+b)，i=0，1，…，a-1.加法是moda的.
定理2.2.6当e≠ei时，χf(Ga，b-e)=a/b.
引理2.2.7a-1/b≤χf(Ga,b-ei)≤a/b，i=0，1，…，a-1.
定理2.2.8当a=kb时，k∈Z且k≥2，有χf(Ga，b-ei)=a/b，i=0，1，…，a-1.
定理2.2.9当a=2b+1时，χf(Ga，b-ei)=a-1/b，i=0，1，…，a-1.
定理2.2.10当a=kb时，k∈Z且k≥2，对图Ga,b中任意不相邻的两顶点vi，vj，有χf(Ga，b∪(vi，vj))=a/b.
定理2.2.11χf(Ga,b∪(vi,vi+1))＞χf(Ga，b)，i=0，…，a-1(va=v0).