康慧君，陈祥恩

(西北师范大学 数学与统计学院，甘肃兰州 730070)

1 准备工作

图的点可区别正常边染色的研究见文献[1-7]，图的点可区别一般边染色的研究见文献[8-9]，图的点可区别正常全染色的研究见文献[10-13]，图的点可区别I-全染色和点可区别VI-全染色的研究见文献[14-19].本文讨论Sm与Sn的联图(3≤m≤n≤n+2)的点可区别I-和VI-全染色.

图G的一个使用了k种颜色的一般全染色(k-一般全染色)是指一个映射f：V∨E→{1,2…,k}.

图G的I-全染色，就是指对于这个图G的一个一般全染色f，∀u,v∈V,有f(u)≠f(v),∀e1,e2∈E,一旦e1与e2相邻，就有f(e1)≠f(e2).

图G的VI-全染色，就是指对于图G的一个一般全染色f，∀e1,e2∈E，一旦e1与e2相邻，就有f(e1)≠f(e2).

设f为图G的k-点可区别I-全染色，若∀u,v∈V(G),u≠v,有C(u)≠C(v)，称f为图G的k-点可区别I-全染色，记为k-VDITC，称为图G的点可区别I-全色数，记为即{k|G有k-VDVITC}.

同理，设f为G的k-点可区别VI-全染色，若∀u,v∈V(G),u≠v,C(u)≠C(v)，称f为图G的k-点可区别VI-全染色，记为k-VDVITC，称为图G的点可区别VI-全色数，记为即{k|G有k-VDVITC}.

设G(V1,E1)与H(V2,E2)，且V1∩V2=∅，E1∩E2=∅,称图G∨H为G与H的联，如果V(G∨H)=V1∪V2,E(G∨H)=E1∪E2∪{uv|u∈V1,v∈V2}.

对于一个简单图G，用ni表示度是i的顶点的个数，δ≤i≤Δ，假设

δ≤i≤i+s≤Δ,s≥0}.

猜想1[14](VDITC猜想)或ξ(G)+1.

猜想2[14](VDVITC猜想)或ξ(G)+1.

引理1[14]对于任意图G，如果存在两个Δ(最大度)顶点，则

引理2[14]

引理3[14]若图G只有一个最大度顶点，且则

引理4[14]如果存在正整数r，δ≤r≤Δ，且G没有度为r的顶点，则

ni+s,δ≤i≤i+s≤r-1,s≥0;或

r+1≤i≤i+s≤Δ,s≥0}.

命题1ξ(G)≤

假设p∈Z，而q为正整数，用(p)q表示{1,2，…，q}中的模q同余于p的那个数，即(p)q∈{1,2，…，q}且(p)q≡p(modq).

关于星与星的联图，有如下定义：

V(Sm∨Sn)={u1,…,um+1,v1,…,vn+1}，E(Sm∨Sn)=

{u1u2,u1u3,…,u1um,u1um+1,v1v2,v1v3，

v1v4,…,v1vn+1}∪{uivj|i=1,2,…,m+1;

j=1,2,…,n+1}.

d(ui)=n+2,i=2,3,…,m+1，度为n+2的点有m个；

d(u1)=m+n+1，d(v1)=m+n+1，度为m+n+1的点有2个；

d(vj)=m+2,j=2,3,…,n+1，度为m+2的点有n个.

2 主要结果

定理1 设Sm∨Sn是星Sm和星Sn的联,3≤m≤n≤n+2,且n=m,n=m+1，则

证明因为Δ(Sm∨Sn)=m+n+1,nΔ≥2由引理1可知，

则需要给出Sm∨Sn的一个(m+n+2)的点可区别I-全染色f.

分如下两种情况考虑：

情况1m=n.

第一步：给连接ui与vj的边进行染色，令

f(uivj)=(i+j-1)n+2，f(uivj)∈{1,2,…，

n+2}，1≤i≤m+1,1≤j≤n+1.

第二……