蛛形图的D(3)-点可区别的全染色

张东翰

(商洛学院数学与计算科学系，陕西商洛726000)

图的染色是图论中最著名和最古老的问题之一，由于其应用的广泛性使得越来越多的学者对其进行了研究.文献［1-3］讨论了图的点可区别的边染色，文献［4］提出了图的距离不大于β的任意2点可区别的边染色并对一些特殊图的色数进行了探讨，文献［5］对特殊图的3，4距离的边染色做了一些研究，文献［6-7］对图的2距离点色数给予了讨论，文献［8-9］对特殊图的全染色进行了研究，文献［10］提出了图的距离不大于β的点可区别的全染色并对一些特殊图的色数进行了探讨，对蛛形图的色数的研究有一定的实际意义，文献［11］讨论了蛛形图的若干染色问题.图的距离染色是图染色研究的热点之一，并已经取得了很多重要的结果.笔者利用构造具体染色的方法，确定了蛛形图的距离不大于3的任意2点可区别的全色数.

1 预备知识

定义1［10］设 G(V，E)是简单图，k 是正整数，f是从 V(G)∪E(G)到 C={1，2，…，k}的映射，若

1)对任意的边 uvE(G)，有 f(u)≠f(v)，f(v)≠f(uv)≠f(v)，

2)对任意的2条相邻的边uv，uw E(G)(v≠w)，有f(uv)≠f(uw)，则称f是图G的一个k-正常全染色(简记作k-PTC)，且称数χT(G)=min{k|图G存在k-PTC}为G的全色数.

设β为正整数，f是图G的一个k-正常全染色，对任意的x V(G)，让C(x)表示在f下点x的颜色以及与x关联的边的颜色构成的集合，称之为点x在f下的色集合.C(x)在全体k种颜色构成的集合中的补集记为(x)，若对任意的u，vV(G)，且u 与v在G 中的距离dG(u，v)≤β，u≠v都有C(u)≠C(v)，那么称f为图G的一个k-D(β)-点可区别全染色(简记为k-D(β)-VDTC)，并将χβ-vt(G)=min{k|G有一个k-D(β)-VDTC}称为图G的D(β)点可区别全色数.

定义2［11］蛛形图Sk的头点为v0，从v0出发有k(k≥3)条路，每条路的长为k，共有n(n=k2+1)个点，删去v0后，得到的彼此不交的k条路分别记为Pi=vi1vi2…vik，(1≤i≤k)，eij表示Pi中连接vi(j-1)和vij(1≤i≤k，2≤j≤k)的边，连接 v0和 vi1的边记为 ei1(1≤i≤k).

引理1［10］设 G 是连通图且|V(G)|≥3，则有(G)，其中ni表示使任意2点间的距离不超过β的度为i的点的最大数目，δ和Δ分别表示图G的最小度和最大度，θ是正整数.

本文中未加述及的术语、记号可参考文献［12-13］.

2 定理及其证明

定理1 设Sk是蛛形图，则有χ3-vt(Sk)=k+1.

证明 当k=3时，μ3=4，根据引理1可知χ3-vt(Sk)≥4，要证明χ3-vt(Sk)=4成立，只需给出一个4-D(3)-VDTC. 现给出一个4-D(3)-VDTC，使用的颜色为 1，2，3，4. 对于边 v0v11，v11v12，v12v13分别用色 1，3，4染;对于边 v0v21，v21v22，v22v23分别用色 2，4，1 染;对于边 v0v31，v31v32，v32v33分别用色 3，4，1 染，对于点 v0用色 4 染，对于点 v11，v12，v13分别用色 2，1，2 染;对于点 v21，v22，v23分别用色 1，3，2 染;对于点 v31，v32，v33分别用色2，3，2染，则此染色是一个正常的全染色，又因为

可知对于距离不大于3的任意2点色集合不同，所以此染色为S3一个4-D(3)-VDTC，因此当k=3时结论成立.

当k≥4时，μ3=k+1，根据引理1可知 χ3-vt(Sk)≥k+1，为了证明 χ3-vt(Sk)=k+1，只需给出一个Sk-(k+1)-D(3)-VDTC，使用的颜色为 1，2，…，k+1，对于边 v0v11，v11v12，…，v1(k-1)v1k分别用色 1，2，3，4，5，…，k 染;对于边 v0vi1，vi1vi2，…，vi(k-1)vik分别用色 i，i+1，…，k，1，2，…，i-1 染 i=2，3，…，k;对于点 v0用色k+1 染;对于点 v11，v12，…，v1(k-1)，v1k分别用色 3，k+1，2，3，…，k-1 染;对于点 v21，v22，…，v2(k-1)，v2k分别用色 4，k+1，3，…，k 染;对于点 v(k-1)1，v(k-1)2，…，v(k-1)(k-1)，v(k-1)k分别用色 1，k+1，k，1，2，…，k-3 染;对于点 vk1，vk2，…，vk(k-1)，vkk分别用色 2，k+1，1，2，…，k-2 染;对于点 vi1，vi2，…，vi(k-1)，vik分别用色 i+2，k+1，i+1，i+2，…，k，1，2，…，i-2 来染 i=3，4，…，k-2，则此染色法为 Sk一个正常的全染色，又因为

且每条路Pi=vi1，vi2，…，vik，(1≤i≤k)上各个边都染不同的颜色，所以在正常全染色下每条路上的任意2点的色集合不同.因此对于距离不大于3的任意2点其色集合不同，所以此染色为一个(k+1)-D(3)-VDTC.当k≥4时结论成立.

综上所述，定理1成立.

［1］BALISTER P N，HUANG Y Q，CHU Y M.Vertex-distinguishng 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-distinguishing proper edge-colorings of graphs［J］.J.of Combin Theory，1999，75:288-301.

［3］BURRIS A C ，SCHELP R H.Vertex-distinguishing proper edge colorings［J］.J.of Graph Theory，1977，26:73-82.

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

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

［6］于兰兰.单圈图的2距离色数［J］.甘肃科学学报，2009，21(3):41-42.

［7］陈海钰，刘信生.最大度为Δ图类的2距离色数的一个下界［J］.甘肃科学学报，2007，19(3):4-5.

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

［9］杨鹏辉.轮形图的全着色［J］.海南大学学报:自然科学版，2011，29(1):8-10.

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

［11］孙亮萍，强会英，孟利冬.蛛形图的若干染色问题［J］.兰州交通大学学报，2011，30(4):41-42.

［12］BONDY J A，MURTY U S R.Graph Theory with Applications［M］.New York:Elsevier Science Publishing Co.，1976.

［13］REINHARD D.Graph Theory［M］.New York:Springer-Verlag，1997.