谭钧铭， 强会英， 姚 丽

(兰州交通大学 数理学院, 甘肃 兰州 730070)`

0 引言

图的染色问题是图论主要研究问题之一，主要包括点染色，边染色和全染色等.自张忠辅教授提出图的邻点可区别边染色，邻点可区别全染色等概念之后，越来越多的学者对图的可区别染色产生了浓厚的兴趣. 2013年，Flandrin等首次提出了图的邻和可区别染色的概念[1]，并给出了邻和可区别边染色的定义. 随后，Monika等给出了邻和可区别全染色的定义[2]. 近几年，不少图论研究者对一些图的广义Mycielski图染色问题[3-6]和图的全染色相关问题[7-10]做了大量研究. 在前人的基础上，本文得出了路和圈的广义Mycielski图的邻和可区别全色数，对研究其他图类的邻和可区别全色数具有重要借鉴意义.

1 预备知识

文中出现的V(G)，E(G)，Δ(G)分别是图G的点集合、边集合、最大度.

定义1[4]设G是拥有m个顶点的简单图，V(G)={v0j|1≤j≤m}，如果满足：

1)V(Mn(G))={v01,v02,…,v0m;v11,v12,…,v1m;…;vn1,vn2,…,vnm}.

2)E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤i,j≤m,i=0,1,2,…,n-1}，

则称Mn(G)为图G的广义Mycielski图.

定义2[9]在图G中，存在一个映射f:V(G)∪E(G)→{1,2,…,k}，若同时满足：

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

2) ∀uv,vw∈E(G)且u≠w,f(uv)≠f(vw);

3) ∀uv∈E(G),f(u)≠f(uv),f(v)≠f(uv);

2 主要结论及证明

证明下面分3种情形证明：

显然，f是Mn(P2)的一个4-NSDTC. 故结论成立.

现根据路图Pm的阶的奇偶性，对各顶点的色集合C(vij)和c(vij)的情况进行如下分类：

此时，c(vij)的情况如表1所示. 易见，f是Mn(Pm)的一个6-NSDTC.

表1 当路的阶为偶数时，C(vij)的情况 表2 当路的阶为奇数时，C(vij)的情况

此时，c(vij)的情况如表2所示. 易见，f是Mn(Pm)的一个6-NSDTC.

综上，结论成立.

情形1 当m≡0(mod2)时,

f(v0jv1,j+1)=f(v0mv11)=2,f(v01v0m)=4,f(v01v1m)=1.

②i≡1(mod6),f(vij)=6(vij≠v1m),f(v1m)=3,f(vijvi+1,j-1)=f(vi1vi+1,m)=5,

③i≡2(mod6),f(vij)=1,f(vijvi+1,j+1)=f(vimvi+1,1)=6,f(vi1vi+1,m)=3.

④i≡3(mod6),f(vij)=5,f(vijvi+1,j-1)=f(vi1vi+1,m)=2,f(vimvi+1,1)=4.

⑤i≡4(mod6),f(vij)=1,f(vijvi+1,j+1)=f(vimvi+1,1)=5,f(vi1vi+1,m)=3.

⑥i≡5(mod6),f(vij)=2,f(vijvi+1,j-1)=f(vi1vi+1,m)=6,f(vimvi+1,1)=4.

⑦i≡0(mod6)且i≠0,f(vij)=1,f(vijvi+1,j+1)=f(vimvi+1,1)=2,f(vi1vi+1,m)=3.

通过以上染色方法，图Mn(Cm)中各顶点的色集合C(vij)与c(vij)的情况为,

此时，c(vij)的情况如表3.

表3 当圈的阶为偶数时，C(vij)的情况 表4 当圈的阶为奇数时，C(vij)的情况

情形2 当m≡1(mod2)时,

f(v01v1m)=1,f(v01v0m)=4,f(v0jv1,j+1)=f(v0mv11)=2.

②i≡1(mod6),f(vij)=6,(vij≠v1m);f(v1m)=3,f(vijvi+1,j-1)=f(vi1vi+1,m)=5,

③i≡2(mod6),f(vij)=1,f(vijvi+1,j+1)=f(vimvi+1,1)=6,f(vi1vi+1,m)=3.

④i≡3(mod6),f(vij)=5,f(vijvi+1,j-1)=f(vi1vi+1,m)=2,f(vimvi+1,1)=4.

⑤i≡4(mod6),f(vij)=1,f(vijvi+1,j+1)=f(vimvi+1,1)=5,f(vi1vi+1,m)=3.

⑥i≡5(mod6),f(vij)=2,f(vijvi+1,j-1)=f(vi1vi+1,m)=6,f(vimvi+1,1)=4.

⑦i≡0(mod6)且i≠0,f(vij)=1,f(vijvi+1,j+1)=f(vimvi+1,1)=2,f(vi1vi+1,m)=3.

按上述染……