兩類完全二部圖的一般點可區別全染色

蘇 麗，陳祥恩，王治文

(1.西北師范大學數學與統計學院，甘肅 蘭州 730070；2.寧夏大學數學計算機科學學院，寧夏 銀川 750021)

0 引言

圖的染色是圖論研究中備受關注的一個課題.點可區別正常全染色在文獻[1-2]中均有研究.文獻[3-4]討論了點可區別IE-全染色問題.點可區別一般全染色在文獻[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).

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

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

2 預備知識

簡單計算，得到如下引理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-子集進行排序，使前k個子集分別為{1}，{2}，{3}，…，{k-3}，{1，k-2}，{1，k-1}，{1，k}.這樣得到的序列共有n項，依次標記這n個子集為D(y1)，D(y2)，…，D(yn).如下構造K4，n的k-一般全染色：

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

(ⅱ) 邊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(yi)={l1，l2}(k+1≤i≤n)是2-子集時，用顏色min[D(yi)∩D(xj)]染邊xjyi，j∈{2，3，4}；用D(yi)中沒有染給邊x2yi的顏色來染邊x1yi和點yi.

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

(ⅴ) 當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(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-1個點的色集合是1-子集，不妨設Cg(yi)={i}，i=1，…，l-1，這將導致Cg(xi)?{1，…，l-1}，則Cg(xi)是{1，…，l-1}或{1，…，l-1，l}(i=1，4)矛盾.如果Y中恰有l-2個點的色集合是1-子集，不妨設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，因此{1，…，l-3，l-2}必是X中某點的色集合.此時{l}，{l-1}，{l-1，l}都不是任一點的色集合，從而可類似得上面結果.

證明令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-子集進行排序，前k個子集分別為{1}，…，{k-4}，{1，k-3}，{1，k-2}，{1，k-1}，{1，k}，得到的序列共有n個項，依次標記這n個子集為D(y1)，…，D(yn).下面構造K5，n的k-一般全染色.

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

(ⅱ) 邊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(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(yi)={l1，l2，l3}是3-子集時，用顏色min[D(yi)∩D(xj)]染邊xjyi，j∈{2，3，4，5}；用D(yi)中沒有染給邊x2yi的兩種顏色來分別染邊x1yi和點yi.

(ⅴ) 當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(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(yi)={l1，…，l6}是6-子集時，用顏色min[D(yi)∩D(x2)]=d染邊x2yi，用顏色min{[D(yi)g0gggggg]∩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-2個點的色集合是1-子集，不妨設Cg(yi)={i}，i=1，…，l-2，這將導致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-3個點的色集合是1-子集，不妨設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中某點的色集合在此處還有四種可能出現的情況：{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}不是任意點的色集合.經計算可得類似上面結果成立.

3 主要結果及其證明