若干倍图的邻点全和可区别全染色

程银万, 杨 超*, 姚 兵

(1.上海工程技术大学数理与统计学院, 智能计算与应用统计研究中心, 上海 201620;2.西北师范大学数学与统计学院, 兰州 730070)

图染色问题是图论中经典问题之一,其研究成果已被广泛应用于通信网络、控制论、计算机科学与编码理论等领域.由于应用的广泛性,许多学者在传统染色的基础上陆续提出了一系列新染色.2004年,Karoński等提出了图的邻和可区别边染色的概念,并给出了该染色下的1-2-3猜想[1].2021年,Przybylo证明了每个d-正则图(d≥2)都是邻和可区别4-边染色的,且当d≥108时,每个d-正则图是邻和可区别3-边染色的[2].2010年,Przybylo和Wozniak将顶点自身的颜色加入其关联边的颜色和中,定义了图的邻和可区别全染色,同时给出了基于邻和可区别全染色的1-2猜想[3].目前,一个较为理想的结果是:任意图的邻和可区别全色数不超过3[4].2017年,Flandrin等在邻和可区别全染色的基础上,将任意一点的所有邻点颜色加入其全染色权重和中,提出了图的邻点全和可区别全染色的概念[5].注意到,Flandrin等在文献[5]中仅将图的邻点全和可区别全染色与邻点被扩展和可区别全染色作了一个简单的对比,并未进行深入研究.近年来,图的邻点全和可区别全染色在文献[6-7]中被进一步研究.受此启发,本文研究路、圈、星、扇、轮、完全二部图以及树的倍图的邻点全和可区别全染色问题．

1 预备知识

本文涉及的图均为连通的简单图,V(G)和E(G)分别表示图G的点集和边集,d(v)表示图中顶点v的度.文中未定义的术语和符号均参考文献[8].下面先介绍与本文有关的定义和概念．

定义1[5]设f：V(G)∪E(G)→[1,k]是图G的一个k-全染色.定义顶点x的权重函数:

(1)

其中,N(x)={y∈V(G)│xy∈E(G)}.对于任意边uv∈E(G),若有φ(u)≠φ(v)成立,则称f是图G的一个邻点全和可区别k-全染色(简记NFSD).图G的邻点全和可区别全染色中最小的k值称为G的邻点全和可区别全色数,记为fgndiΣ(G)．

定义2[9]设G′是简单图G的拷贝,记G的顶点为ui,G′相应的顶点为vi,若图D(G)满足:

1)V(D(G))=V(G)∪V(G′);

2)E(D(G))=E(G)∪E(G′)∪{uivj│ui∈V(G),vj∈V(G′),uiuj∈E(G)},

则称D(G)为G的倍图．

当n=3时,路P3的倍图D(P3)如图1所示.

图1 倍图D(P3)Fig.1 Double graph D(P3)

2 主要结论及证明

定理1若图G中存在度相同的相邻点,则fgndiΣ(G)≥2．

证明(反证法)假设图G中存在度相同的相邻点u,v,即d(u)=d(v).若图G中的点和边均染颜色1,则由公式(1)得φ(u)=φ(v)=2d(u)+1=2d(v)+1,与定义1相矛盾,故fgndiΣ(G)≥2．

定理2设Pn=u1u2u3…un表示n(n≥1)阶的路,当n=1,3时,fgndiΣ(D(Pn))=1;其他情形,fgndiΣ(D(Pn))=2.

证明由定义2知,当n=1,3时,图D(Pn)中不存在度相同的相邻点,所以,当D(Pn)中所有点和边都染颜色1时,不存在相邻点权重相同的情况,符合定义1.当n≠1,3时,由定理1知,至少需要2种颜色才可以完成对图D(Pn)的邻点全和可区别全染色.下面给出对图D(Pn)的点和边的具体染色．

定义D(Pn)的一个全染色f1：V(D(Pn))∪E(D(Pn))→[1,2]如下:

f1(ui)=f1(vi)=1,1≤i≤n,ui,vi∈V(D(Pn));

f1(e)=2,其中,e∈{uiui+1│i≡1,2(mod 4)}∪{vivi+1│i≡0,3(mod 4)};

f1(e0)=1,e0∈E(D(Pn)){e}．

染色f1代入公式(1),可得图D(Pn)中各点的权重如下.

情形1n≡0(mod 4).

情形2n≡1(mod 4).

情形3n≡2(mod 4).

情形4n≡3(mod 4).

因为各相邻点权重不同,所以f1为D(Pn)的一个NFSD-2-全染色.

定理3设Cn=u1u2u3…unu1表示阶数为n(n≥3)的圈,则fgndiΣ(D(Cn))=2．

证明根据定理1,由于图D(Cn)中存在度相同的相邻点,所以至少需要2种颜色才能完成对D(Cn)的邻点全和可区别全染色.下面分4种情形对D(Cn)的点和边进行染色．

情形1n≡0(mod 4).

定义D(Cn)的一个全染色f2：V(D(Cn))∪E(D(Cn))→[1,2]如下:

f2(ui)=f2(vi)=1,1≤i≤n,ui,vi∈V(D(Cn));

f2(e)=2,e∈{uiui+1,vivi+1│i≡2,3(mod 4)};

f2(e0)=1,e0∈E(D(Cn)){e}．

由染色f2可得图D(Cn)中各点的权重如下:

情形2n≡1(mod 4).

定义D(Cn)的一个全染色f3：V(D(Cn))∪E(D(Cn))→[1,2]如下:

ui,vi∈V(D(Cn));f3(e)=2,e∈{uiui+1,vivi+1│i≡1,2(mod 4),i≠1};f3(e0)=1,e0∈E(D(Cn)){e}．

由染色f3可得图D(Cn)中各点的权重如下:

情形3n≡2(mod 4).

定义D(Cn)的一个全染色f4：V(D(Cn))∪E(D(Cn))→[1,2]如下:

1≤i≤n,ui,vi∈V(D(Cn));f4(e)=2,e∈{uiui+1,vivi+1│i≡0,3(mod 4)};f4(e0)=1,e0∈E(D(Cn)){e}．

由染色f4可得图D(Cn)中各点的权重如下:

情形4n≡3(mod 4).

定义D(Cn)的一个全染色f5：V(D(Cn))∪E(D(Cn))→[1,2]如下:

ui,vi∈V(D(Cn));f5(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4),i≠1};f5(e0)=1,e0∈E(D(Cn)){e}．

由染色f5可得图D(Cn)中各点的权重如下:

因为各相邻点权重不同,所以f2,f3,f4,f5分别为各情形下D(Cn)的一个NFSD-2-全染色.

定理4设Sn表示阶数为n+1(n≥3)的星,则fgndiΣ(D(Sn))=1．

证明设Sn的点集和边集分别为:V(Sn)={u1,u2,…,un+1},E(Sn)={uiun+1│1≤i≤n}.由定义2知,图D(Sn)为完全二部图,即D(Sn)=K2,2n.根据定理1,图D(Sn)中不存在度相同的相邻点,所以只需要一种颜色就可以完成图D(Sn)的邻点全和可区别全染色,即fgndiΣ(D(Sn))=1．

定理5设Fn表示阶数为n+1(n≥3)的扇,则fgndiΣ(D(Fn))=2．

证明设Fn的点集和边集分别为:V(Fn)={u1,u2,…,un+1},E(Fn)={uiun+1│1≤i≤n}∪{uiui+1│1≤i≤n-1}.由定义2知,图Fn中存在度相同的相邻点,所以至少需要两种颜色才可以完成Fn的邻点全和可区别全染色.具体全染色方案f6：V(D(Fn))∪E(D(Fn))→[1,2]如下:

f6(ui)=f6(vi)=1,1≤i≤n+1;f6(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4)};f6(e0)=1,e0∈E(D(Fn)){e}．

由染色f6可得如下三种情形图Fn中各点的权重．

情形1n≡0,3(mod 4).

情形2n≡1(mod 4).

情形3n≡2(mod 4).

因为各情形下相邻点权重不同,所以f6为D(Cn)的一个NFSD-2-全染色．

定理6设Wn表示阶数为n+1(n≥3)的轮,则fgndiΣ(D(Wn))=2．

证明设Wn的点集和边集分别为:V(Wn)={u1,u2,…,un+1},E(Wn)={uiun+1│1≤i≤n}∪{uiui+1│1≤i≤n-1}∪{unu1}.以下分两种情形证明．

情形1n=3.

定义染色f7：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f7(vi)=1,1≤i≤n+1;f7(e)=2,e∈{u1u2,u1v2,u1v4,u2v4,u3v4,v2v4,v3v4};f7(e0)=1,e0∈E(D(Wn)){e}．

由染色f7可得各点权重如下:

φ(u1)=17,φ(u2)=16,φ(u3)=15,φ(u4)=14,φ(v1)=13,φ(v2)=16,φ(v3)=15,φ(v4)=19．

因为相邻点权重不同,所以f7为D(W3)的一个NFSD-2-全染色．

情形2n≥4.

1)当n≡0(mod 4)时,定义染色f8：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f(ui)=f(vi)=1,1≤i≤n+1;

f(e)=2,e∈{uiui+1,vivi+1│i≡2,3(mod 4)};

f(e0)=1,e0∈E(D(Cn)){e}．

由染色f8可得各点权重如下:

2)当n≡1(mod 4)时,定义染色f9：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f9(e)=2,e∈{uiui+1,vivi+1│i≡1,2(mod 4),i≠1};f9(e0)=1,e0∈E(D(Wn)){e}．

由染色f9可得各点权重如下:

3)当n≡2(mod 4)时,定义染色f10：V(D(Wn))∪E(D(Wn))→[1,2]如下:

f10(e)=2,e∈{uiui+1,vivi+1│i≡0,3(mod 4)};f10(e0)=1,e0∈E(D(Wn)){e}．

由染色f10可得各点权重如下:

4)当n≡3(mod 4) 时,定义染色f11：V(D(Wn))∪E(D(Wn))→[1,2]如下:

1≤i≤n+1;f11(e)=2,e∈{uiui+1,vivi+1│i≡0,1(mod 4),i≠1};f11(e0)=1,e0∈E(D(Wn)){e}．

由染色f11可得各点权重如下:

因为各情形下相邻点权重不同,所以f8、f9、f10、f11分别为各情形下D(Cn)的一个NFSD-2-全染色．

定理7设Km,n(m≥1,n≥1)表示完全二部图,则fgndiΣ(D(Km,n))=2(m=n);fgndiΣ(D(Km,n))=1(m≠n).

证明令V(Km,n)=X∪Y,E(Km,n)={uivj│1≤i≤m,1≤j≤n},其中X={u1,u2,…,um},Y={v1,v2,…,vn}.首先,完成对完全二部图的邻点全和可区别全染色,其次,通过倍图的连接特征发现,完全二部图Km,n的倍图D(Km,n)即为完全二部图K2m,2n.下面分两种情形证明．

情形1m=n．

定义染色f12：V(Km,n)∪E(Km, n)→[1,2]如下:

f12(ui)=1,f12(vi)=2,f12(uivj)=1,1≤i≤m,1≤j≤n．

由上述染色f12可得各点权重如下:

φ(ui)=3m+1,φ(vi)=2m+2.

观察发现,仅当m=1时,φ(ui)=φ(vi),而其倍图K2m,2n的点集X、Y的阶数均大于等于2,故对于图K2m,2n,φ(ui)≠φ(vi)恒成立．

情形2m≠n.

定义染色f13：V(Km,n)∪E(Km,n)→[1,2]如下:

f13(ui)=f13(vi)=f13(uivj)=1,1≤i≤m,1≤j≤n.

由染色f13可知,φ(ui)=2n+1,φ(vi)=2m+1.

所以,此情形下,φ(ui)≠φ(vi)恒成立．

上述两种情形表明完全二部图Km,n的邻点全和可区别全色数是确定的.由于Km,n的倍图D(Km,n)也是完全二部图,所以f12和f13分别是各情形下的一种NFSD-全染色．

定理8设T表示n(n≥3)阶树.若树T中不存在度相同的相邻点,则fgndiΣ(D(T))=1;若树T中存在度相同的相邻点,则fgndiΣ(D(T))=2.

证明当树T中不存在度相同的相邻点时,树的倍图中也不存在度相同的相邻点,根据定理1,仅需1种颜色就可以完成树倍图的邻点全和可区别全染色.下面讨论树中存在度相同的相邻点情形,首先通过构建树染色算法完成树的邻点全和可区别全染色;其次结合树倍图的结构特点进行分析证明.树的邻点全和可区别全染色算法如下.

步骤1树T中每个顶点染颜色1．

步骤2对树T中边的染色定义如下两种染色方式.

f14(eu):对顶点u的所有未染色的邻边分配颜色2;

f15(eu):对顶点u的一条未染色的邻边分配颜色1,其余邻边染颜色2．

步骤3选择树T中任一度数为奇数的顶点,记为u.即d(u)≡1(mod 2).对u的邻边选择染色方式f14(eu)．

步骤4设ui为点u的邻点．

当d(ui)≡1(mod 2)时,采用染色方式f15(eui);

当d(ui)≡0(mod 2)时,采用染色方式f14(eui)．

步骤5设uij为点ui的邻点．当d(ui)≡0(mod 2)时,

若d(uij)≡1(mod 2),采用染色f14(euij);

若d(uij)≡0(mod 2),采用染色f15(euij)．

当d(ui)≡1(mod 2)且f(uiuij)=2时,

若d(uij)≡1(mod 2),采用染色方式f14(euij);

若d(uij)≡0(mod 2),采用染色方式f15(euij)．

当d(ui)≡1(mod 2)且f(uiuij)=1时,

若d(uij)≡1(mod 2),采用染色方式f15(euij);

若d(uij)≡0(mod 2),采用染色方式f14(euij)．

步骤6设uijk为点uij的邻点．当d(ui)≡1(mod 2)且d(uij)≡1(mod 2)且f(uijuijk)=1时,

若d(uijk)≡0(mod 2),采用染色方式f15(euijk);

若d(uijk)≡1(mod 2),采用染色方式f14(euijk)．

当d(ui)≡1(mod 2)且d(uij)≡1(mod 2)且f(uijuijk)=2时,

若d(uijk)≡0(mod 2),采用染色方式f14(euijk);

若d(uijk)≡1(mod 2),采用染色方式f15(euijk)．

其他情况下的边染色依照步骤5．

步骤7继续上述过程,直至树T的边都被染了颜色1或2．

完成上述的树染色过程,树中相邻顶点的权重是奇偶可分的,即相邻点的权重不同.假设树T′是树T的复制,其染色方式和树T保持一致,且树T和T′之间的连线都染颜色1,观察树倍图的结构发现,此时D(T)中顶点的权重均增加了2d(u)+1,由于2d(u)+1是奇数,所以树T和T′中的顶点权重的奇偶性均发生了变化.但是,D(T)中相邻点的权重依然是奇偶可分的,即相邻点权重不同.假设树T中的叶子节点为vi,那么染色后图D(T)中φ(vi)≤6,而与vi相邻的次结点的权重大于等于9,所以叶子结点的权重小于内点权重恒成立.综上所述,两种颜色可以完成D(T)的邻点全和可区别全染色．