K1,1,p,K1,2,p的点可区别的IE-全染色及一般全染色

2018-03-27寇艳芳陈祥恩王治文

吉林大学学报(理学版) 2018年2期

关键词：矛盾

寇艳芳, 陈祥恩, 王治文

(1. 西北师范大学数学与统计学院, 兰州 730070; 2. 宁夏大学数学计算机科学学院, 银川 750021)

0 引言

目前, 关于点可区别一般边染色的研究已有很多结果[1-6]. 点可区别未必正常的全染色也得到广泛关注：文献[7]提出了点可区别IE-全染色; 文献[8]提出了一般点可区别全染色.

本文考虑K1,1,p,K1,2,p的点可区别IE-全染色和一般点可区别全染色, 并给出其点可区别IE-全色数和一般点可区别全色数. 本文假设完全三部图Km,n,p的顶点集合为V=X∪Y∪Z, 其中X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp}, 边集合为

当m=1时, 记X={x}; 当n=1时, 记Y={y}. 本文约定提及一个图的l-VDIETC或l-GVDTC时, 总认为所使用的l种颜色为1,2,…,l.

1 预备知识

由于一个图的点可区别IE-全染色一定是点可区别一般全染色, 因此下列结论显然成立.

下面给出K1,1,p的一个k-IE-全染色f. 令f(x)=1,f(y)=2. 用maxD(zi)染点zi(i=1,2,…,p). 将zi的关联边均染以i+2(i=1,2,…,l-2). 对|D(zi)|=2, 用min{D(x)∩D(zi)}染边xzi, min{D(y)∩D(zi)}染边yzi; 对|D(zi)|=3, 用min{D(y)∩D(zi)}染边yzi, min{[D(x)∩D(zi)]f(yzi)}染边xzi; 用min{D(x)∩D(y)}染边xy. 最后所得K1,1,p的l-IE全染色f是点可区别的, 因为∀v∈V(K1,1,p), 均有C(v)=D(v).

矛盾. 因此x的色集合不是1-子集. 同理,Y中点的色集合也不是1-子集.

下面给出K1,2,p的一个l-IE-全染色f. 令f(x)=1,f(y)=2. 用maxD(zi)染点zi(i=1,2,…,p). 而zi的关联边均染以i+2(i=1,2,…,l-2). 对|D(zi)|=2，用min{D(x)∩D(zi)}染边xzi, 用min{D(yi)∩D(zi)}染边yjzi,j=1,2; 对|D(zi)|=3, 用min{D(x)∩D(zi)}染边xzi, 用min{[D(yj)∩D(zi)]f(xzi)}染边yjzi,j=1,2; 对|D(zi)|=4, 用min{D(x)∩D(zi)}染边xzi, 用min{[D(y1)∩D(zi)]f(xzi)}染边y1zi, 用min{[D(y2)∩D(zi)]f(xzi)f(y1zi)}染边y2zi; 用min{D(x)∩D(yj)}染边xyj,j=1,2. 最后所得K1,2,p的l-IE全染色f是点可区别的, 因为∀v∈V(K1,2,p), 均有C(v)=D(v).

注1K1,2,27的6-VDIETC可由K1,2,28的6-VDIETC限制在{x,y1,y2,z1,z2,…,z27}上得出;K1,2,26的6-VDIETC可由K1,2,28的6-VDIETC限制在{x,y1,y2,z1,z2,…,z26}上得出.

下面给出K1,2,p的GVDTCf. 令f(x)=f(yj)=k(j=1,2). 用maxD(zi)染点zi(i=1,2,…,p). 至于边的染色，与引理4中边的染色相同.

2 主要结果

证明：分以下7种情形讨论:

下面给出K1,1,p的GVDTCf. 令f(x)=f(y)=k. 用maxD(zi)染点zi(i=1,2,…,p). 将zi的关联边均染以i+1(i=1,2,…,k-1). 对|D(zi)|=2, 用min{D(x)∩D(zi)}染边xzi, min{D(y)∩D(zi)}染边yzi; 对|D(zi)|=3, 用min{D(y)∩D(zi)}染边yzi, min{[D(x)∩D(zi)]f(yzi)}染边xzi; 用min{D(x)∩D(y)}染边xy.