K1,1,p,K1,2,p的點可區別的IE-全染色及一般全染色

寇艷芳, 陳祥恩, 王治文

(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.

情形3)K1,1,13沒有4-GVDTC.

情形4)p=11,12.

此時,K1,1,p沒有4-VDIETC. 假設K1,1,11有4-VDIETCg, 不妨設g(x)=1,g(y)=2, 則Z中每個點的色集合是下列11個子集{3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4}之一, 且以上11個點集均為Z中點的色集合. 從而{1,3,4}∈Cg(x), {2,3,4}∈Cg(y), 表明Cg(x)=Cg(y)={1,2,3,4}, 矛盾. 由引理2知,K1,1,p(p=11,12)的5-VDIETC可由K1,1,22的5-VDIETC限定在{x,y,z1,z2,…,zp}導出的子圖上得到, 因此存在5-VDIETC.

另一方面,K1,1,p沒有3-GVDTC({1,2,3}共有7個非空子集, 無法區別p+2個點), 但可以給出其4-GVDTC如下. 令D(x)={1,2,3,4},D(y)={2,3,4},D(zi)={i+1}(i=1,2,3),D(z4)={1,4}. 將{1,2,3,4}的除{1,4}外的2-子集、 3-子集排成一個序列S5, 令D(z5),D(z6),…,D(z12)依次是S5中的第1,2,…,8項, 據此可參照情形1)中的染色方法給出K1,1,12的4-GVDTC. 對K1,1,11的4-GVDTC, 只需將K1,1,12的4-GVDTC限制在{z1,z2,…,z11}上即可得到.

情形5) 5≤p≤10.

情形6)p=3,4.

先證K1,1,p沒有3-VDIETC. 假設K1,1,3存在3-VDIETCg, 不妨設g(x)=1,g(y)=2, 則Z中頂點必用3來染色,Z中每個點的色集合只能是{3},{1,3},{2,3},{1,2,3}之一. 若Z中某個頂點的色集合為{3}, 則圖K1,1,p每個點的色集合必為{3},{1,3},{2,3},{1,2,3}之一, 矛盾; 若{3}不是Z中任意頂點的色集合, 此時只能p=3, 且Z中3個點的色集合分別為{1,3},{2,3},{1,2,3}, 從而{1},{2},{3}不是任意頂點的色集合, 矛盾.K1,1,p的4-VDIETC可由情形5)中K1,1,10的4-VDIETC限定在由{x,y,z1,z2,…,zp}(p=3,4)導出的子圖上得到.

另一方面,K1,1,p沒有2-GVDTC({1,2}共有3個非空子集, 不能區分(p+2)個點), 存在3-GVDTC(其染色易得).

情形7)p=1,2.

此時顯然K1,1,p沒有2-GVDTC, 存在3-VDIETC(其染色易得).

證明： 分下列8種情形討論:

情形3) 27≤p≤53.

先證K1,2,p沒有5-GVDTC. 假設K1,2,p有5-GVDTC, 由引理3的證明可知, 1-子集只能是Z中頂點的色集合, 顯然{1},{2},{3},{4},{5}不全是Z中點的色集合. 不妨設{1}不是Z中任意點的色集合, 若{2},{3},{4},{5}均是Z中點的色集合, 則{2,3,4,5}?C(x), {2,3,4,5}?C(yj)(j=1,2), 矛盾. 因此存在a∈{2,3,4,5}, 使得{a}不是Z中任意點的色集合, 不妨設a=2, 則{3,4,5}?C(x), {3,4,5}?C(yj)(j=1,2),C(x),C(y1),C(y2)是集合{3,4,5},{1,3,4,5},{2,3,4,5},{1,2,3,4,5}之一. 無論是哪3種組合, 均矛盾.

情形4)K1,2,26沒有4-GVDTC(與情形3)的證明類似), 由引理5中2)可知K1,2,26有5-GVDTC.

情形5) 當11≤p≤25時,K1,2,p沒有4-GVDTC(與情形3)的證明類似). 但可構造K1,2,25的5-VDIETCf如下.

情形6) 3≤p≤9.

情形7)K1,2,10沒有3-GVDTC(類似情形6)的討論), 但有4-GVDTC, 構造如下.

令D(x)={1,2,3,4},D(y1)={2,3,4},D(y2)={1,3,4},D(zi)={i+2}(i=1,2),D(z3)={1,4},D(z4)={2,4}. 將{1,2,3,4}的除D(x),D(y1),D(y2),D(z3),D(z4)外的2-子集、 3-子集、 4-子集排成一個序列S9. 令D(z5),D(z6),…,D(z10)依次是S9中的第1,2,…,6項. 據此可參照引理5中的染色方法給出K1,2,10的4-GVDTC.

情形8)K1,2,2沒有2-GVDTC({1,2}共有3個非空子集, 不能區分p+3個頂點), 但存在3-GVDTC(其染色易得). 同時,K1,2,2沒有3-VDIETC. 否則, 若K1,2,2有3-VDIETCg, 不妨設g(x)=1,g(y1)=g(y2)=2(由情形1)的證明知g(y1),g(y2)只能相同), 則Z中頂點必用3染色. 若Z中某個點的色集合為{3}, 則K1,2,2的每個點的色集合必為{3},{1,3},{2,3},{1,2,3}之一, 矛盾; 若Z中任意頂點的色集合不為{3}, 則此時只能p=3, 且Z中3個點的色集合分別為{1,3},{2,3},{1,2,3}, 從而{1},{2},{3}不是任意頂點的色集合, 矛盾. 但K1,2,2存在4-VDIETC(其染色易得).

[1] Harary F, Plantholt M. The Point-Distinguishing Chromatic Index [M]. New York: Wiley Interscience, 1985: 147-162.

[5] Salvi N Z. On the Value of the Point-Distinguishing Chromatic Index ofKn,n[J]. Ars Combinatoria, 1990, 29B: 235-244.

[6] CHEN Xiang’en. Point-Distinguishing Chromatic Index of the Union of Paths [J]. Czechoslovak Mathematical Journal, 2014, 64(3): 620-640.

[7] CHEN Xiang’en, GAO Yuping, YAO Bing. Vertex-Distinguishing IE-Total Colorings of Complete Bipartite GraphsKm,n(m

[8] LIU Chanjuan, ZHU Enqiang. General Vertex-Distinguishing Total Coloring of Graphs [J/OL]. Journal of Applied Mathematics, 2014-08-03. http://dx.doi.org/10.1155/2014/849748.