蘇 麗，陳祥恩，王治文

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

0 引言

圖的染色是圖論研究中備受關(guān)注的一個課題.點可區(qū)別正常全染色在文獻(xiàn)[1-2]中均有研究.文獻(xiàn)[3-4]討論了點可區(qū)別IE-全染色問題.點可區(qū)別一般全染色在文獻(xiàn)[5]中被提出.

一個圖G使用k種顏色1，2，…，k的一般全染色是指從V∪E到{1，2，…，k}的一個映射.一個圖G的IE-全染色是指從V∪E到{1，2，…，k}的一個映射f，使得對任意相鄰頂點u和v，f(u)≠f(v).

設(shè)f為G的一個一般全染色(或IE-全染色)，x為G的一個頂點，記C(x)={f(xu)|xu∈E}∪{f(xu)}，稱之為頂點x在f下的色集合.設(shè)f為G的一般全染色(或IE-全染色)，若對u，v∈V，u≠v，總有C(u)≠C(v)，則f稱為圖G的點可區(qū)別一般全染色或者一般點可區(qū)別全染色(或點可區(qū)別IE-全染色)，簡記為GVDTC(或VDIETC).令

文獻(xiàn)[6]研究了完全二部圖K2，n及K3，n的一般點可區(qū)別全染色，確定了它們的一般點可區(qū)別全色數(shù).本文將探討完全二部圖K4，n及K5，n的一般點可區(qū)別全染色.

2 預(yù)備知識

簡單計算，得到如下引理1和引理2：

證明令D(x1)={1，2，3，…，k}，D(x2)={1，2，3，…，k-2，k-1}，D(x3)={1，2，3，…，k-2，k}，D(x4)={1，2，3，…，k-3，k-1，k}.將{1，2，3，…，k}的除{k}，{k-1}，{k-2}外的所有1-子集、2-子集、3-子集、4-子集和5-子集進(jìn)行排序，使前k個子集分別為{1}，{2}，{3}，…，{k-3}，{1，k-2}，{1，k-1}，{1，k}.這樣得到的序列共有n項，依次標(biāo)記這n個子集為D(y1)，D(y2)，…，D(yn).如下構(gòu)造K4，n的k-一般全染色：

(ⅰ) 當(dāng)D(yi)={l}是1-子集時，用顏色l染點yi和它的關(guān)聯(lián)邊.

(ⅱ) 邊x1yk-2，x2yk-2，x3yk-2染以k-2，而x4yk-2染以顏色1；邊x1yk-1，x2yk-1，x4yk-1染以k-1，而x3yk-1染以1；邊x1yk，x3yk，x4yk染以k，而x2yk染以1.

(ⅲ) 當(dāng)D(yi)={l1，l2}(k+1≤i≤n)是2-子集時，用顏色min[D(yi)∩D(xj)]染邊xjyi，j∈{2，3，4}；用D(yi)中沒有染給邊x2yi的顏色來染邊x1yi和點yi.

(ⅳ) 當(dāng)D(yi)={l1，l2，l3}是3-子集時，用顏色min[D(yi)∩D(xj)]染邊xjyi，j∈{2，3，4}；用D(yi)中沒有染給邊x2yi的兩種顏色分別來染邊x1yi和點yi.

(ⅴ) 當(dāng)D(yi)={l1，l2，l3，l4}是4-子集時，用顏色min[D(yi)∩D(x2)]=a染邊x2yi，用顏色min{[D(yi){a}]∩D(x3)}=b染邊x3yi，用顏色min[D(yi)∩D(x4)]染邊x4yi，用D(yi){a，b}中的兩種顏色分別來染邊x1yi和點yi.

(ⅵ) 當(dāng)D(yi)={l1，l2，l3，l4，l5}是5-子集時，用顏色min[D(yi)∩D(x2)]=s染邊x2yi，用顏色min{[D(yi){s}]∩D(x3)}=t染邊x3yi，用顏色min{[D(yi){s，t}]∩D(x4)}=p染邊x4yi，用D(yi){s，t，p}中的兩種顏色分別來染邊x1yi和點yi.

(ⅶ) 用顏色k染點x1，x3，x4，用顏色k-1染點x2.

如果Y中至少有l(wèi)-1個點的色集合是1-子集，不妨設(shè)Cg(yi)={i}，i=1，…，l-1，這將導(dǎo)致Cg(xi)?{1，…，l-1}，則Cg(xi)是{1，…，l-1}或{1，…，l-1，l}(i=1，4)矛盾.如果Y中恰有l(wèi)-2個點的色集合是1-子集，不妨設(shè)Cg(yi)={i}，i=1，…，l-2，則Cg(xi)={1，…，l-1，l}，{1，…，l-1}，{1，…，l-2，l}，{1，…，l-3，l-2}，i=1，4，因此{(lán)1，…，l-3，l-2}必是X中某點的色集合.此時{l}，{l-1}，{l-1，l}都不是任一點的色集合，從而可類似得上面結(jié)果.

證明令D(x1)={1，…，k}，D(x2)={1，…，k-1}，D(x3)={1，…，k-2，k}，D(x4)={1，…，k-3，k-1，k}，D(x5)={1，…，k-4，k-2，k-1，k}.對{1，…，k}的除{k}，{k-1}，{k-2}，{k-3}外的所有1-子集、2-子集、3-子集、4-子集、5-子集和6-子集進(jìn)行排序，前k個子集分別為{1}，…，{k-4}，{1，k-3}，{1，k-2}，{1，k-1}，{1，k}，得到的序列共有n個項，依次標(biāo)記這n個子集為D(y1)，…，D(yn).下面構(gòu)造K5，n的k-一般全染色.

(ⅰ) 當(dāng)D(yi)={l}是1-子集時，用顏色l染點yi和它的關(guān)聯(lián)邊.

(ⅱ) 邊x1yk-3，x2yk-3，x3yk-3，x4yk-3染以k-3，而x5yk-3染以min[D(x5)∩D(yk-3)]；邊x1yk-2，x2yk-2，x3yk-2，x5yk-2染以k-2，而x4yk-2染以min[D(x4)∩D(yk-2)]；邊x1yk-1，x2yk-1，x4yk-1，x5yk-1染以k-1，而x3yk-1染以min[D(x3)∩D(yk-1)]；邊x1yk，x3yk，x4yk，x5yk染以k，而x2yk染以min[D(x2)∩D(yk)].

(ⅲ) 當(dāng)D(yi)={l1，l2}(k+1≤i≤n)是2-子集時，用顏色min[D(yi)∩D(xj)]染邊xjyi，j∈{2，3，4，5}；用D(yi)中沒有染給邊x2yi的顏色來染邊x1yi和點yi.

(ⅳ) 當(dāng)D(yi)={l1，l2，l3}是3-子集時，用顏色min[D(yi)∩D(xj)]染邊xjyi，j∈{2，3，4，5}；用D(yi)中沒有染給邊x2yi的兩種顏色來分別染邊x1yi和點yi.

(ⅴ) 當(dāng)D(yi)={l1，l2，l3，l4}是4-子集時，用顏色min[D(yi)∩D(x2)]=a染邊x2yi，用顏色min{[D(yi){a}]∩D(x3)}=b染邊x3yi，用顏色min[D(yi)∩D(x4)]染邊x4yi，用顏色min[D(yi)∩D(x5)]染邊x5yi，用D(yi){a，b}中的兩種顏色分別來染邊x1yi和點yi.

(ⅵ) 當(dāng)D(yi)={l1，l2，l3，l4，l5}是5-子集時，用顏色min[D(yi)∩D(x2)]=s染邊x2yi，用顏色min{[D(yi){s}]∩D(x3)}=t染邊x3yi，用顏色min{[D(yi){s，t}]∩D(x4)}=p染邊x4yi，用顏色min[D(yi)∩D(x5)]染邊x5yi，用D(yi){s，t，p}中的兩種顏色分別來染邊x1yi和點yi.

(ⅶ) 當(dāng)D(yi)={l1，…，l6}是6-子集時，用顏色min[D(yi)∩D(x2)]=d染邊x2yi，用顏色min{[D(yi)syggg00]∩D(x3)}=e染邊x3yi，用顏色min{[D(yi){d，e}]∩D(x4)}=f染邊x4yi，用min{[D(yi){d，e，f}]∩D(x5)}=g染邊x5yi，用D(yi){d，e，f，g}中的兩種顏色分別染邊x1yi和點yi.

(ⅷ) 用顏色k-3染點x1，用顏色k-1染點x2，用顏色k染點x3，x4，x5.

如果Y中至少有l(wèi)-2個點的色集合是1-子集，不妨設(shè)Cg(yi)={i}，i=1，…，l-2，這將導(dǎo)致Cg(xi)?{1，…，l-2}，則Cg(xi)是{1，…，l-2}，{1，…，l-2，l-1}，{1，…，l-2，l}，{1，…，l-2，l-1，l}，i=1，4，5，矛盾.如果Y中恰有l(wèi)-3個點的色集合是1-子集，不妨設(shè)Cg(yi)={i}，i=1，…，l-3，則Cg(xi)={1，…，l-1，l}，{1，…，l-1}，{1，…，l-2，l}，{1，…，l-3，l-1，l}.對于X中某點的色集合在此處還有四種可能出現(xiàn)的情況：{1，…，l-3，l-2}，{1，…，l-3，l-1}，{1，…，l-3，l}，{1，…，l-3}，i=1，4，5.此時{l}、{l-1}、{l-2}、{l-1，l}，或{l}、{l-1}、{l-2}、{l-2，l}，或{l}、{l-1}、{l-2}、{l-2，l-1}，或{l}、{l-1}、{l-2}、{l-2，l-1，l}不是任意點的色集合.經(jīng)計算可得類似上面結(jié)果成立.

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