K1，5，p和 K1，6，p的點(diǎn)可區(qū)別的IE-全染色及一般全染色

寇艷芳 ，陳祥恩 ，王治文

(1. 西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 甘肅 蘭州 730070； 2. 寧夏大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 寧夏 銀川 750021)

0 引 言

點(diǎn)可區(qū)別一般邊染色由HARARY等[1]于1985年提出，在文獻(xiàn)[1-6]中均有涉及．

近年來，點(diǎn)可區(qū)別的未必正常的全染色也得以研究.CHEN等[7]提出了點(diǎn)可區(qū)別IE-全染色，而LIU等[8]提出了一般點(diǎn)可區(qū)別全染色．

本文研究K1，5，p和K1，6，p的點(diǎn)可區(qū)別IE-全染色和一般點(diǎn)可區(qū)別全染色，并給出了其點(diǎn)可區(qū)別IE-全色數(shù)和一般點(diǎn)可區(qū)別全色數(shù).其完全三部圖Km，n，p的頂點(diǎn)集合為V=X∪Y∪Z,其中，X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp},邊集合為{xiyj|i=1，2,…,m;j=1，2,…,n}∪{yjzt|j=1，2,…,n;t=1，2,…,p}∪{xizt|i=1，2,…,m;t=1，2,…,p},當(dāng)m=1時，記X={x}．

約定文中圖的l-VDIETC或l-GVDTC所使用的l種顏色為1，2,…,l，令A(yù)l={1，2,…,l}．

1 準(zhǔn)備工作

一個圖的點(diǎn)可區(qū)別IE-全染色一定是點(diǎn)可區(qū)別一般全染色，因此下述命題成立．

下面給出K1，5，p的一個l-IE-全染色f.令f(x)=1,f(yj)=2,j=1，2,…，5;用maxD(zi)染點(diǎn)zi，i=1，2,…,p.而zi的關(guān)聯(lián)邊均染以i+5,i=1，2,…,l-5.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi，min[D(yj)∩D(zi)]染邊yjzi,j=1，2,…，5;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi,min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1，2,…，5;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,min[(D(yj))∩D(zi){f(xzi),f(y1zi)}]染邊yjzi,j=2,3,4，5;對|D(zi)|=s(5≤s≤7),用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…,min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3,…,s-2;min[D(yj)∩D(zi)]染邊yjzi,j=s-1,s,…，5;min[D(x)∩D(yj)]染邊xyj,j=1,2,…，5．

最后得到K1，5，p的l-IE全染色f是點(diǎn)可區(qū)別的，因為對?v∈V(K1，5，p),均有C(v)=D(v)．

假設(shè){3},{4},…,{r-1}均為Z中點(diǎn)的色集合，那么{2，3,…,r-1}?C(yj),j=1，2,…,n,矛盾．不妨設(shè){3}為非Z中任意點(diǎn)的色集合，當(dāng)n=5時，有以下2種情況:

(i) {4},{5},…,{r-1}中有一個非Z中任意點(diǎn)的色集合.不妨設(shè){4}為非Z中任意點(diǎn)的色集合，這樣{1},{2},{1，2},{3},{4}均非Z中點(diǎn)的色集合,那么除這5個子集外，Ar-1的其他1-子集，2-子集，…，7-子集均為Z中點(diǎn)的色集合，特別地，單元集{5}，{6}，…，{r-1}及{1，3}，{1，4}，{2，3}，{2，4}，{3，4}均為Z中點(diǎn)的色集合.那么{2，5，6,…,k-1}?C(yj)(j=1，2,…，5),且C(yj)含1，3，4中的至少某2種色.故每個C(yj)是Ar-1,Ar-1{1},Ar-1{3},Ar-1{4}之一，矛盾．

(ii) {4},{5},…,{r-1}均為Z中點(diǎn)的色集合.則{1，4,…,r-1}?C(x)，{2，4,…,r-1}?C(yj)(j=1，2,…，5),這樣每個C(yj)為Ar-1，Ar-1{1}，Ar-1{3},Ar-1{1，3}之一,矛盾．

當(dāng)n=6時，有以下3種情況:

(i) 當(dāng){4},{5},…,{r-1}均為Z中點(diǎn)的色集時,同上可推出矛盾．

下設(shè)k=5,在K1，6，19的5-GVDTC下，{1，2，3，4，5}的所有2-子集，3-子集，4-子集，5-子集恰好構(gòu)成K1，6，19的全體頂點(diǎn)的色集合.每個2-子集及其補(bǔ)集不屬于不同部的2個頂點(diǎn)的色集合，每個2-子集及其補(bǔ)集只能同時是Y中點(diǎn)的色集合或同時都是Z中點(diǎn)的色集合.當(dāng)然有某個2-子集是Z中點(diǎn)的色集合.不妨設(shè){1，2}∈{C(z)|z∈Z},那么{3，4},{3，5},{4，5}∈{C(z)|z∈Z}，進(jìn)而{1，5},{2，5},{1，4},{2，4},{1，3},{2，3}∈{C(z)|z∈Z},從而10個2-子集及其補(bǔ)集都必須是Z中點(diǎn)的色集合，但Z中僅有19個頂點(diǎn)，矛盾．

下面給出K1，6，p的一個l-IE-全染色f.令f(x)=1,f(yj)=2,j=1，2,…，6;用maxD(zi)染點(diǎn)zi，i=1，2,…,p.而zi的關(guān)聯(lián)邊均染以i+6,i=1，2,…,l-6.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi，min[D(yj)∩D(zi)]染邊yjzi,j=1，2,…，6;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi,min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1，2,…，6;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,min[(D(yj)∩D(zi)){f(xzi),f(y1zi)}]染邊yjzi,j=2,3,…，6;對|D(zi)|=s′(5≤s′≤8),用min[D(x)∩D(zi)]染邊xzi,min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…,min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3,…,s′-2;min[D(yj)∩D(zi)]染邊yjzi,j=s′-1,s′,…，6;min[D(x)∩D(yj)]染邊xyj,j=1,2,…，6．

最后得到K1，6，p的l-IE全染色f是點(diǎn)可區(qū)別的，因為對?v∈V(K1，6，p),均有C(v)=D(v)．

2 主要結(jié)果及其證明

(ii)χgvt(K1，5，p)=

證明分以下幾種情形進(jìn)行討論:

下面給出K1，5，p的k-GVDTCf.令f(x)=f(yj)=k,j=1，2,…，5;用maxD(zi)染點(diǎn)zi，i=1，2,…,p.而zi的關(guān)聯(lián)邊均染以i+5,i=1，2,…,k-5.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi，min[D(yj)∩D(zi)]染邊yjzi,j=1，2,…，5;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi,用min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1，2,…，5;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi,用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,用min[(D(yj)∩D(zi)){f(xzi),f(y1zi)}]染邊yjzi,j=2,3,…，5;對|D(zi)|=q(5≤q≤7),用min[D(x)∩D(zi)]染邊xzi,用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…,用min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3,…,q-2;用min[D(yj)∩D(zi)]染邊yjzi,j=q-1,q,…，5;用min[D(x)∩D(yj)]染邊xyj,j=1,2,…，5．

情形3當(dāng)p=496時，在引理1(i)中令k=9,得K1，5，496無8-GVDTC.而K1，5，496的10-VDIETC可由引理2中的染色規(guī)則得到．

同時K1，5，495的9-VDIETC的構(gòu)造類似于引理2，不再詳述．

情形5K1，5，244無8-VDIETC.只要在引理3的證明過程中令r=9便可得.但其有9-VDIETC(可由K1，5，494的9-VDIETC限制在{x,y1,…,y5,z1,…,z244}上得到).同時,在引理1(i)中令k=8，可知K1，5，244無7-GVDTC,其8-GVDTC可依照情形1構(gòu)造．

情形6117≤p≤243.先證K1，5，p無7-GVDTC.在引理1(ii)中令k=7,可知K1，5，117無7-GVDTC．但K1，5，p有8-VDIETC,K1，5，243的8-VDIETC的構(gòu)造類似于引理2．

情形7K1，5，116無7-VDIETC.只要在引理3的證明過程中令r=8便可得.但它有8-VDIETC，可通過將K1，5，243的8-VDIETC限制在{x,y1,…,y5,z1,…,z116}上得到.同時，在引理1(ii)中令k=6，可知K1，5，116無6-GVDTC.而7-GVDTC可依照情形1構(gòu)造．

情形853≤p≤115.先證K1，5，p無6-GVDTC.在引理1(ii)中令k=6,可知K1，5，53無6-GVDTC．但K1，5，p有7-VDIETC,K1，5，115的7-VDIETC的構(gòu)造類似于引理2．

情形9K1，5，52無6-VDIETC.只要在引理3的證明過程中令r=7便可得.但其有7-VDIETC，可通過將K1，5，115的7-VDIETC限制在{x,y1,…,y5,z1,…,z52}上得到.同時，在引理1(ii)中令k=5，可知K1，5，52無5-GVDTC,有6-GVDTC,可依照情形1構(gòu)造．

情形1021≤p≤51.先證K1，5，p無5-GVDTC.在引理1(ii)中令k=5,可知K1，5，21無5-GVDTC．但K1，5，p有6-VDIETC,K1，5，51的6-VDIETC構(gòu)造類似于引理2．

情形11K1，5，20無5-VDIETC.只要在引理3的證明過程中令r=7便可得.但其有6-VDIETC，可通過將K1，5，51的6-VDIETC限制在{x,y1,…,y5,z1,…,z20}上得到.同時，K1，5，20無4-GVDTC(否則，{1，2，3，4}的非空子集不能區(qū)分諸頂點(diǎn))，但有5-GVDTC,可依照情形1構(gòu)造．

(ii)χgvt(K1，6，p)=

證明分以下幾種情形討論:

下面給出K1，6，p的k-GVDTCf.令f(x)=f(yj)=k,j=1，2,…，6;用maxD(zi)染點(diǎn)zi，i=1，2,…,p.而zi的關(guān)聯(lián)邊均染以i+6,i=1，2,…,k-6.對|D(zi)|=2,用min[D(x)∩D(zi)]染邊xzi，用min[D(yj)∩D(zi)]染邊yjzi,j=1，2,…，6;對|D(zi)|=3,用min[D(x)∩D(zi)]染邊xzi，min[(D(yj)∩D(zi)){f(xzi)}]染邊yjzi,j=1，2,…，6;對|D(zi)|=4,用min[D(x)∩D(zi)]染邊xzi，用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,用min[(D(yj)∩D(zi)){f(xzi),f(y1zi)}]染邊yjzi,j=2,3，…，6;對|D(zi)|=q′(5≤q′≤8),用min[D(x)∩D(zi)]染邊xzi,用min[(D(y1)∩D(zi)){f(xzi)}]染邊y1zi,…，用min[(D(yj)∩D(zi)){f(xzi),f(y1zi),…,f(yj-1zi)}]染邊yjzi,j=2,3，…,q′-2;用min[D(yj)∩D(zi)]染邊yjzi,j=q′-1,q,…，6;用min[D(x)∩D(yj)]染邊xyj,j=1,2,…，6．

情形2當(dāng)p=1 006時，在引理4(i)中令k=10,得K1，6，504無9-GVDTC,那么K1，6，1 006無9-GVDTC．

而K1，6，p有10-VDIETC,其染色類似于引理5，不再贅述．

情形4K1，6，498無9-VDIETC.只要在引理3的證明過程中令r=10便可得.但其有10-VDIETC,可通過將K1，6，1 005的10-VDIETC限制在{x,y1,…,y6,z1,…,z498}上得到.同時，在引理4(ii)中令k=8，可知K1，6，498無8-GVDTC,有9-GVDTC,可依照情形1構(gòu)造．

情形5當(dāng)243≤p≤497時，先證K1，6，p無8-GVDTC.在引理4(ii)中令k=8，可知K1，5，243無8-GVDTC.但K1，6，p有9-VDIETC,K1，6，497的9-VDIETC構(gòu)造類似于引理5．

情形6K1，6，242無8-VDIETC.只要在引理3的證明過程中令r=9則可得.但其有9-VDIETC，可通過將K1，6，497的9-VDIETC限制在{x,y1,…,y6,z1,…,z242}上得到.同時，在引理4(ii)中令k=7，可知K1，6，242無7-GVDTC,有8-GVDTC,可依照情形1構(gòu)造．

情形7當(dāng)115≤p≤241時，先證K1，6，p無7-GVDTC.在引理4(ii)中令k=7，可知K1，6，115無7-GVDTC.但K1，6，p有8-VDIETC,K1，6，241的8-VDIETC構(gòu)造類似于引理5．

情形8K1，6，114無7-VDIETC.只要在引理3的證明過程中令r=8便可得.但其有8-VDIETC，可通過將K1，6，241的8-VDIETC限制在{x,y1,…,y6,z1,…,z114}上得到.同時，在引理4(ii)中令k=6，可知K1，6，114無6-GVDTC,有7-GVDTC,可依照情形1構(gòu)造．

情形9當(dāng)51≤p≤113時，在引理4(ii)中令k=6,可知K1，6，51無6-GVDTC.但K1，6，p有7-VDIETC，K1，6，113的7-VDIETC構(gòu)造類似于引理5．

情形10K1，6，50無6-VDIETC.只要在引理3的證明過程中令r=7便可得.但其有7-VDIETC，可通過將K1，6，113的7-VDIETC限制在{x,y1,…,y6,z1,…,z50}上得到.同時，在引理4(ii)中令k=5，可知K1，6，50無5-GVDTC,有6-GVDTC,可依照情形1構(gòu)造．

情形11當(dāng)19≤p≤49時，在引理4(ii)中令k=5,可知K1，6，19無5-GVDTC.但K1，6，p有6-VDIETC，K1，6，49的6-VDIETC構(gòu)造類似于引理5．

情形12當(dāng)p=18時，K1，6，18無5-VDIETC.只要在引理3的證明過程中令r=6便可得.但其有6-VDIETC，可通過將K1，6，49的6-VDIETC限制在{x,y1,…,y6,z1,…,z18}上得到.同時易證K1，6，18無4-GVDTC，而有5-GVDTC.將{1，2，…，5}的所有5-子集，4-子集，3-子集，2-子集依次分配給X，Y，Z中點(diǎn)的色集合，可得其染色(25-1-5>p+7)．

對于一般的完全三部圖的VDIETC與GVDTC，筆者正在進(jìn)一步探索中．