若干图的邻点可区别的I-全染色和邻点可区别的I-均匀全染色

张 婷， 赵慧霞， 杜 佳， 赵双柱

(兰州文理学院 a.教育学院, b.学报编辑部, c.数字媒体学院, 甘肃 兰州 730000)

0 引 言

图的染色起源于地图着色问题，它是图论中的一个重要分支，其基本问题之一就是确定各种染色法的色数. 图G的I-全染色是指对图G的顶点和边进行染色,使得任意两个相邻顶点的颜色不同,任意两条相邻边的颜色不同. 图G的一个邻点可区别的I-全染色是指:在图G的I-全染色的基础上，还满足任意两个相邻顶点的色集合不同,即C(u)≠C(v),其中,C(u)={f(u)|u∈V(G)}∪{f(uv)|uv∈E(G),v∈V(G)}.而图的邻点可区别的I-全染色中所用颜色的最少数量称为图G的邻点可区别I-全色数. Zhang等[1]于2009年提出了图的邻点可区别I-全染色概念, 拓展了图染色理论的应用领域. 之后, 一些学者对一些特殊图的邻点可区别I-全染色和点可区别I-全染色进行了研究[2 - 6]. 文献[2]研究了Pm∨Sn,Sm∨Fn,Sm∨Sn和Sm∨Wn的邻点可区别I-全染色，得到了它们的邻点可区别I-全色数; 文献[3]给出了路、扇和星的Mycielski图的邻点可区别I-全色数,文献[4]研究并给出了若干倍图邻点可区别I-全色数.

图的均匀染色强调了任意两个色类的颜色个数最大相差为1,它常用来解决一些分配、调度及负载平衡问题. 均匀染色的概念最早是由Meyer[7]于1973年提出的,这个概念的提出揭开了图的均匀染色的序幕, Fu[8]于1994年提出了均匀全染色概念及均匀全染色猜想, 1996年，Zhang[9]独立地提出了图的均匀全色数概念.他们在研究了一些简单图的均匀全色数之后，提出了均匀全染色猜想:任意简单图的均匀全色数至多为最大度加2,自此揭开了图的均匀全染色研究的序幕. 2015年，王继顺[10]得到了路、圈、扇、轮、完全图和完全二部图的邻点可区别I-均匀全色数，并提出邻点可区别I-均匀全色数最大不超过Δ(G)+2的猜想. 之后，许多学者围绕图的均匀全染色问题做了大量研究[11 - 13].文献[14]研究了若干Mycielski图的邻点可区别的I-均匀全染色, 文献[15]研究了几类特殊图的邻点可区别I-均匀全染色. 本文根据路、圈、星、扇和轮的平方图的构造特征,研究并确立了它们邻点可区别I-均匀全色数,验证了它们的色数满足猜想给出了图C5∨Wn的邻点可区别的I-全染色,进一步补充了文献[2].

定义1[10]若连通图G(V,E)的阶|V(G)|≥2,f是从V(G)∪E(G)到{1,2,…,k}的映射，k是自然数，若f满足以下三点：

(1)对∀uv∈E(G),u≠v,有f(u)≠f(v);

(2)对∀uv,uw∈E(G),v≠w,f(uv)≠f(uw);

(3)对∀uv∈E(G),u≠v,C(u)≠C(v),

定义2[10]若连通图G(V,E)的阶|V(G)|≥2且f是G(V,E)的一个k-I-AVDTC，若f满足∀i,j∈{1,2,…k},i≠j,有||Ti|-|Tj||≤1，则称f为G的一个k-邻点可区别I-均匀全染色(简记为k-I-AVDETC),称=min{k|存在G的k-I-AVDETC}为G的邻点可区别I-均匀全色数，其中，Ti=Vi∪Ei,Vi={v|v∈V(G),f(v)=i},Ei={e|e∈E(G),f(e)=i}.

定义3[10]对于一个简单图G，V(Gk)=V(G),E(Gk)=E(G)∪{uv|d(uv)≤k}，其中，d(uv)是u和v的距离.当k=2时,称此图为G的平方图.

定义4[2]两个不相交图的联图就是把一个图G(V1,E1)的每个顶点与另一个图H(V2,E2)的每个顶点连接起来所得到的图，记作G(V1,E1)∨H(V2,E2), 其中，

V=V1∪V2,E=E1∪E2∪{uv|u∈V1,v∈V2}.

引理1[10]若连通图G的阶|V(G)|≥2,则有表示G的最大度.

引理2[10]若连通图G的阶|V(G)|≥2,且G有相邻的最大度点,则有

引理3[10]设Kn为n(n≥3)阶完全图，则

猜想1[10]对简单连通图G,有

文中未加说明的符号或术语参见文献[16].

1 路、圈、星、扇和轮的平方图的邻点可区别I-均匀全色数

本部分根据路、圈、星、扇和轮的平方图的构造特征,研究并确立了它们邻点可区别I-均匀全色数.

定理1设Pn为n(n≥3)阶的路，则有

证明以下分四种情形证明本定理.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合：

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合:

令f为点v1,v2,…,vn用1,2,3,4,0循环着色；边v1v2,v2v3,…,vn-1vn用0,1,2,3,4循环着色；边v1v3,v2v4,…,vn-2vn用3,4,0,1,2循环着色.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合:

(i=2,3,…,n-2);

当n≡0(mod5)时，

当n≡2(mod5)时，

当n≡4(mod5)时，

从而此染色法是均匀的.

定理2对n阶的圈Cn,当n≥4时,有

情形1当n≡0(mod5)时,令f为v1,v2,…,vn用1,2,3,4,0循环着色；v1v2,v2v3,…,vn-1vn,vnv1用3,4,0,1,2循环着色；v1v3,v2v4,…,vn-2vn,vn-1v1,vnv2用1,2,3,4,0循环着色.

情形2当n≡1(mod5)时,令f为点v1,v2,…,v6用1,2,3循环着色；点v7,v8,…,vn用4,0,1,2,3循环着色；边v1v2,v2v3,…,v6v7用4,0循环着色；边v7v8,v8v9,…,vn-1vn,vnv1用1,2,3,4,0循环着色； 边v1v3,v2v4,…,v5v7,v6v8用1,2,3循环着色； 边v7v9,v8v10,…,vn-1v1,vnv2用4,0,1,2,3循环着色.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合:

情形3当n≡2(mod5)时,令f为点v1,v2,…,v7用0,1,3,4,0,1,2着色；点v8,v9,…,vn用0,1,2,3,4循环着色；边v1v2,v2v3,…,v7v8用4,0,1,2,1,2,3着色；边v8v9,v9v10,…,vn-1vn,vnv1用4,0,1,2,3循环着色； 边v1v3,v2v4,…,v7v9用2,3,3,4,4,0,1着色；边v8v10,v9v11,…,vn-1v1,vnv2用2,3,4,0,1循环着色.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合:

情形4当n≡3(mod5)时,令f为点v1,v2,…,v8用1,2,3,0,2,1,3,0着色；点v9,v10,…,vn用4,1,2,3,0循环着色；边v1v2,v2v3,…,v8v9用4,0,4,1,4,3,4,2着色；边v9v10,v10v11,…,vn-1vn,vnv1用1,2,3,4,0循环着色； 边v1v3,v2v4,…,v8v10用1,2,3,0,2,1,0,3着色；边v9v11,v10v12,…,vn-1v1,vnv2用4,0,1,2,3循环着色.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合:

情形5当n≡4(mod5)时,令f为点v1,v2,…,v9用4,2,1,4,3,0,1,2,3着色,点v10,v11，…,vn用4,0,1,2,3循环着色,边v1v2,v2v3，…,v9v10用1,2,3,2,3,4,0,4,0着色,边v10v11,v11v12,…,vn-1vn,vnv,用1,2,3,4,0循环着色,边v1v3,v2v4,…,v9v11用4,4,0,0,1,1,2,3,3着色, 边v10v12,v11v13,…,vn-1v1,vnv2用4,0,1,2,3循环着色.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合:

定理3对n+1阶的星Sn,扇Fn,轮Wn,有

2 C5∨Wn的邻点可区别I-全色数

本部分根据C5∨Wn的构造特征, 给出了C5∨Wn的邻点可区别I-全色数.

定理4对m阶的圈Cm和n+1阶的轮Wn，当m=5时，有

情形1当n=3时，图C5∨W3中有相邻的最大度点,且Δ(C5∨W3)=8，由引理2知，为证定理为真,只需给出图C5∨W3的一个9-I-AVDTC,为此构造映射f：V(C5∨W3)∪E(C5∨W3)→{1,2,…,9},令f为

f(ui)=i+3,i=1,2,…,5;f(v0)=9;

f(vj)=j,j=1,2,3;

f(uivj)=(i+j+3)9,i=1,2,…,5;j=0,1,2,3;

f(uiui+1)=i,i=1,2,3,4;

f(u5u1)=3;f(v0vj)=j,j=1,2,3;f(v1v2)=3;

f(v2v3)=5;f(v1v3)=4.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合：

可见,C5∨W3的9个顶点的色集合彼此互异,由定义,f是C5∨W3的一个5-I-AVDTC.

情形2当n≥4时,图C5∨Wn只有一个最大度点,且Δ(C5∨Wn)=n+5,由引理1知,为证成立,只需给出图C5∨Wn的一个n+5-I-AVDTC,为此构造映射f：V(C5∨Wn)∪E(C5∨Wn)→{1,2,…,n+5},以下分三种情况证明.

情形2.1当n=4时，令f为

f(ui)=n+i,i=1,2,3;

f(ui)=n+i-2,i=4,5;

f(v0)=n+5;f(vj)=j,j=1,2,…n;

f(uiv0)=n+i,i=1,2,…,5;

f(uivj)=i+j,i=1,2,…,5;

j=1,2,…,n-1;

f(v0vj)=j,j=1,2,…n;

f(uivn)=n+i+1,i=1,2,3;

f(u4vn)=2;f(u5vn)=5;

f(u1u2)=f(u3u4)=f(v2v3)=f(v1v4)=9;

f(u2u3)=f(u5u1)=f(v3v4)=1;

f(u4u5)=3;f(v1v2)=8.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合:

可见C5∨Wn, 当n=4时的10个顶点的色集合彼此互异,由定义,f是C5∨Wn(n=4)的一个n+5-I-AVDTC.

情形2.2当n=5时，令f为

f(ui)=n+i,i=1,2,3;

f(ui)=n+i-2,i=4,5;f(v0)=n+5;

f(vj)=j,j=1,2,…n;

f(uiv0)=n+i,i=1,2,…,5;

f(uivj)=i+j,i=1,2,…,5;j=1,2,…,n-1;

f(uivn)=n+i+2,i=1,2,3;

f(u4vn)=1;f(u5vn)=4;

f(u1u2)=10;f(uiui+1)=i-1,i=2,3,4;

f(u5u1)=1;f(v0vj)=j,j=1,2,…n;

f(vjvj+1)=n+2+j,j=1,2,3;

f(v4v5)=2;f(v5v1)=7.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合：

可见,C5∨Wn,当n=5时的11个顶点的色集合彼此互异,由定义,f是C5∨Wn(n=5)的一个n+5-I-AVDTC.

情形2.3当n>5时,令f为

f(ui)=n+i+1,i=1,2,3;

f(ui)=n+i-1,i=4,5;f(v0)=n+5;

f(vj)=j,j=1,2,…n-1;f(vn)=n+1;

f(uiv0)=n+i,i=1,2,…,5;

f(uivj)=i+j,i=1,2,…,5;j=1,2,…,n-1;

f(uivn)=(n+i+2)(n+5),i=1,2,…,5;

f(u1u2)=n+5；f(uiui+1)=i-1,i=2,3,4;

f(u5u1)=1;f(v0vj)=j,j=1,2,…n;

f(v1v2)=n+5；f(vjvj+1)=j-1,j=1,2,…n-1;

f(v1vn)=n+2.

为验证上述染色法f是邻点可区别的，现列出各顶点的色集合：

C(v1)={1,2,…,6,n+2,n+5};

C(v2)={1,2,…,7,n+5};

C(vj)={j-2,j-1,…,j+5},j=3,4,…,n-1;

C(vn)={1,2,n-2,n,…,n+5}.

可见,C5∨Wn,当n>5时的n+6个顶点的色集合彼此互异,由定义,f是C5∨Wn(n>5)的一个n+5-I-AVDTC.

综上，定理得证.