蛛形图的全染色和星全染色

张东翰

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

图的染色是图论中最著名和最古老的问题之一，由于其应用的广泛性使得越来越多的人对其进行了研究,文献[1-2]研究了一些特殊图的全染色，文献[3-5]研究了一些特殊图的星全染色，文献[6]讨论了蛛形图的一些染色问题。图的全染色和星全染色是图染色研究的热点之一，并已经取得了很多重要的结果。鉴于此，本文对蛛形图的全染色和星全染色进一步探讨。

1 定义及引理

定义1[1-2]设 G（V，E）是简单图，k 是自然数，f是从 V(G)∪E(G)到{1,2,3,…,k}的映射，如果满足：

1)对任意的边 uv∈E(G)，f（u）≠f（v）,f（u）≠f（uv）≠f（v）。

2)对任意的两相邻的边uv，uw∈E(G)(v≠w),f（uv）≠f(vw)。

则称f是图G的一个正常全染色(简记作k-PTC)，且称数 XT(G)=min｛k-STC｝为 G 的全色数。

定义2[3-5]图G的一个k-正常全染色叫做k-星全染色（简记为k-STC），如果图G的任何路长为2的点和边的着色均不相同，则称Xst(G)=min{k|图G的k-STC}为G的星全染色。

定义3[6]蛛形图Sk的头点为v0，从v0出发有 k(k≥3)条路，每条路有 k 个点，共有 n（n=k2+1）个点，删去v0后，这k条路分别记为Pi=vi1，vi2，…，vik,(1≤i≤k),eij表示 Pi中连接 vi(j-1)和 vij(1≤i≤k,2≤j≤k)的边，连接 v0和 vi1的边记为 ei1(1≤i≤k)。

引理1[1-2]对于任意的简单图G都有XT(G)≥△(G)+1。

引理2[2-5]对于任意的简单图G都有是图G的最大度，X'(G)是图G的边色数。本文中未加述的术语、记号可在文献[7]中找到。

2 定理及其证明

定理1 设Sk是蛛形图，则有XT(Sk)=k+1。

证明：因为△(Sk)=k,根据引理1可知XT(Sk)≥k+1,为了证明定理1成立只需给出一个（k+1）-PTC即可,设色集合 C={0，1，2,…,k}。对于点 v11,v12，…,v1k用色 2,1 循环染,对于点 v1i,vi2，…,vik,i=2,…,k,用色1,2循环染，对于v0点用色0来染；对于边v0v11,v0v21,…,v0vk1分别用色 1,2,…,k,来染；对于边vi1vi2,vi2vi3,…,vi（k-1）vik,i=1,2,用色3,4循环染；对于边 vi1vi2,vi2vi3,…,vi（k-1）vik,i=4,5,…,k，用色 3,4 循环染；对于边 v31v32,v32v33,…,v3(k-1)v3k，用色 4，3 循环染；则此染色法为一个正常的全染色,所以此定理成立。

定理2设Sk是蛛形图，则有Xst(Sk)=2k+1。

证明：因为△(Sk)=k,根据引理2可知Xst(Sk)≥2k+1,为了证明定理2成立只需给出一个（2k+1）-STC即可,设色集合 C={1，2，…,2k+1}。对于点 v11，v12，…,v1k用色k+1,3,4循环染；对于点v21,v22,…,v2k用色k+2,3,4循环染；对于点v31,v32,…,v1k,用色k+1,3,4循环染；对于点v21,v22,…,v2k用色k+2,3,4循环染；对于点v31,v32,…,v3k,用色k+3,4,5循环染；对于点v41,v42,…,v4k,用色 k+4,5,6 来染；对于点 vi1,vi2,…,vik,i=5,…,k用k+i,3,4循环染，对于点v0用色2k+1来染；对于边v0v11,v0v21,…,v0vk1分别用色1,2,…,k来染；对于边v11v12,v12v13,…,v1(k-1)v1k用色2,1循环染；对于边vi1vi2,vi2vi3,…,vi(k-1)vik,i=2,3,…,k用色1,i循环染；则此染色法为一个正常的星全染色,所以此定理成立。

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

[2]陈 亮.图的全染色及邻点可区别的全染色[D].重庆大学,2007.

[3]马庆媛,田双亮.若干联图的星全染色[J].西北民族大学学报,2010,31(4):16-18.

[4]强会英,李沐春,张忠辅.星和扇图的广义Mycielski的星全染色[J].兰州理工大学学报,2009,33(3):306-308.

[5]张 婷,强会英,李沐春.关于图的星全染色[J].数学的实践与认识,2008,38(18):160-163.

[6]孙亮萍,强会英,孟利冬.蛛形图的若干染色问题[J].兰州交通大学学报,2011,30(4):128-130.

[7]Bondy JA,Murty USR.Graph Theory with Applications[M].New York:The Macmillan Press Ltd,1976.