路的D（3）-点可区别的全染色

张东翰，朱 白

(商洛学院 数学与计算机应用学院，陕西商洛 726000)

图的染色是图论中最著名和最古老的问题之一，由于其应用的广泛性使得越来越多的人对其进行了研究,文献[1-3]讨论了图的点可区别的边染色，文献[4]提出了图的距离不大于β的任意两点可区别的边染色并对一些特殊图的色数进行了探讨，文献[5-7]对特殊图的2，3，4距离的染色做了一些研究，文献[8]对特殊图的全染色进行了研究，文献[9]提出了图的距离不大于β的点可区别的全染色并对一些特殊图的色数进行了探讨,文献[10]研究了蛛形图的D（3）-点可区别的全染色。图的距离染色是图染色研究的热点之一，并已经取得了很多重要的结果。通过对大量文献的研读，研究了路的距离不大于3的点可区别的全染色。

1 定义及引理

定义1[8-9]设G(V，E)是简单图，k是正整数，f是从 V(G)∪E(G)到 C={1，2，…，k}的映射，如果满足：

1）对任意的边 uν∈E(G)，f(u)≠f(ν)f(u)≠f(uν)≠f(ν)；

2）对任意的两相邻的边uν,uw∈E(G)(ν≠w),f(uν)≠f(νw)；则称 f是图 G 的一个正常全染色(简记作 k-PTC)，且称数为G的全色数。

如果f是一个k正常全染色，并且满足：

3）对任意的 u,ν∈V(G)，u≠ν,dG(u,ν)≤β,其中dG(u,ν)表示u与ν的距离，β是正整数，有C(u)≠C(ν)，也就是

显然，当β=1时，D(1)-点可区别的全染色是邻点可区别的全染色，当 β=diam(G)时，D(β)-点可区别的全染色是点可区别的全染色，其中diam(G)表示图 G 的直径，且分别用 χat(G)和 χνt(G)表示χ1νt(G)χdνt(G)，其中 d=diam(G)。

引理1[9]设G是连通图且，则有，χβνt≥μβ(G),其中称为图G的组合度，ni表示使任意两点间的距离不超过β的度为i的点的最大数目，δ和△分别表示图G的最小度和最大度，θ是正整数。

引理2[9]设G是连通图且，那么有χat(G)≤χβνt(G)≤χdνt(G)。

猜想1[9]对于阶数不小于2的简单连通图G，有 χβνt(G)≤μβ(G)+1。

2 定理及其证明

定理1 设Pn是n(n≥4)阶的路，则有 χνt(Pn)=4。

证明：当n≥4时，μ3（Pn）=4，根据引理1可知χ3νt（Pn）≥4，要证明χ3νt（Pn）=4成立，只需给出一个 4-D（3）-VDTC，设色集合 C={1，2，3，4}，Pn=ν1ν2·…·νn-1νn，现给出一个 4-D（3）-VDTC，对于边ν1ν2,ν2ν3,…,νn-1νn分别用色 3，4，1，2 循环染；对于点 ν1，ν2，…，νn分别用色 1，2，3，4 循环染，则此染色法是一个正常的全染色，又因为当2≤i≤n-1且i≡0(mod4)时（νi）={3}；2≤i≤n-1且i≡1(mod4)时（νi）={4}；当2≤i≤n-1且i≡2(mod4)时，（νi）={1}；当2≤i≤n-1且i≡3(mod4)时，C（νi）={2}；当n=4时（νi）={2,4}（ν4）={2,3}，当n≥5时，dG（νi,νn）≥4,由此可知，对于距离不大于 3 的任意两点色集合不同，所以此染色法为一个4-D(3)-VDTC，因此定理成立。

[1]BalisterP N,HuangY Q,Chu YM.Vertexdistinguishng edge colorings of graphs[J].J of Graph Theory,2003,42:95-109.

[2]Bazgan C,Harat—Benhamdie A,Li H,et al.On the vertex-distinguishng edge colorings of graphs[J].J of Combin Theory,1999,75:288-301.

[3]Burris A C,Schelp R H.Vertex-distinguishng proper edge colorings[J].J of Graph Theory,1977,26:73-82.

[4]张忠辅,李敬文,陈祥恩,等.图的距离不大于β的任意两点可区别的边染色[J].数学学报:中文版,2006,49(3):703-708.

[5]于兰兰.单圈图的距离色数[J].甘肃科学学报,2009,21(3):41-42.

[6]陈海钰,刘信生.最大度为△图类的距离色数的一个下界[J].甘肃科学学报,2007,19(3):4-5.

[7]田京京.路和圈的距离不大于3和4的点可区别的边染色[J].兰州理工大学学报,2008,34(4):156-158.

[8]张东翰.路的广义Mycielski图的全染色[J].商洛学院学报,2012,26(2):9-10.

[9]张忠辅,李敬文,陈祥恩,等.图的距离不大于β的点可区别的全染色[J].中国科学:A辑,2006,36(10):1119-1130.

[10]张东翰.蛛形图的D(3)-点可区别的全染色[J].海南大学学报：自然科学版,2013,31(4):300-302.