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

2013-08-15 00:47张东翰
商洛学院学报 2013年6期
关键词:用色商洛条路

张东翰

(商洛学院 数学与计算科学系,陕西商洛 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.

猜你喜欢
用色商洛条路
这条路
陕西商洛:创出菌蔬轮种发展新模式
浅析苏州博物馆新馆的建筑特点
“墨点无多泪点多”
这条路
我的是故乡商洛
平面设计中用色要素探究
商洛加快培育千亿元新能源汽车产业集群
多点执业这条路还没有修好
这条路