完全二部圖K10，n（215≤n≤466）的點可區別E-全染色

包麗婭，陳祥恩*，王治文

（1.西北師范大學數學與統計學院,甘肅 蘭州730070；2.寧夏大學數學統計學院,寧夏 銀川750021）

0 引言

關于圖的點可區別全染色已有許多研究[1-4]。圖G的一個E-全染色f是指使相鄰點著以不同的色，且任意一個頂點與它的關聯邊著以不同顏色的全染色。設f為G的一個E-全染色,如果對任意的互不相同的頂點u,v∈V(G),有C(u)≠C（v）,那么稱f為圖G的點可區別E-全染色，簡稱為VDET 染色。令{k|G存在k-VDET 染色}，稱為圖G的點可區別E-全色數。

文獻[5]探討了星、輪、扇、路、圈、完全圖,完全二部圖K2,n的VDET 染色。文獻[6]得到mC3和mC4的VDET 色數。文獻[7-9]討論了完全二部圖K3,n,K4,n,K5,n的VDET 染色。文獻[10]討論了完全二部圖K7,n的VDET 染色。文獻[11-12]討論了完全二部圖K10,n的VDET 染色。本文主要討論K10,n(215≤n≤466)的VDET 染色，并 得到了K10,n(215≤n≤466)的VDET 色數。

引理1[11]當10≤n≤90時，有

引理2[12]當91≤n≤214時,有

引理3[12]K10,214存在一個9-VDET 染色:X中頂點u1,u2,…,u10的色集合分別為頂點u1,u2,…,u10的顏色分別為1,2,1,2,1,2,2,2,1,2,Y中頂點的色集合分別為{1,2,3,4,5,6,7,8}的7-子集、6-子集、5-子集、4-子集、3-子集、2-子集，但不是前面已經出現的X中頂點的色集合,不是含1 或含2的2-子集,不是{5,6},{1,5,6},{2,5,}6 ,{1,2,5,6},也不是同時含1和2的3-子集。

1 主要結果及證明

定理1當215≤n≤466時,有

證明先證K10,n不存在8-VDET 染色。假設K10,n有8-VDET 染色f，所用顏色為1，2，…，8。考慮下面7種情形。

情形1u1,u2,…,u10的顏色當中互不相同的僅有1種。不妨設f(ui)=1,i=1,2,…,10,則每個C(vj)不包含顏色1，從而可以作為Y中頂點色集合{1,2,3,4,5,6,7,8}的子集數目為當215≤n≤466時，128個集合不能區分Y中的n個頂點，矛盾。

情形2u1,u2,…,u10的顏色當中互不相同的僅有2種。不妨設f(ui)∈{1,2},i=1,2,4,…,10。則當C(vj)是2-子集時，C(vj)不包含顏色1 或2，從而可以作為Y中頂點色集合的{1,2,3,4,5,6,7,8}的子集的數目為當235≤n≤466時，234個集合不能區分Y中的n個頂點，矛盾。

下設215≤n≤234。令B=B1∪B2∪B3,C(Y)?B,其中，

B3是{1,2,3,4,5,6,7,8}的4-子集、5-子集、6-子集、7-子集、8-子集和不在B2中的3-子集構成的集合。

發現B中包含i的成員有120個，i=1,2;B中包含j的成員有125個，j=3,4,…,8。因此，每個C(ui)至少包含3種顏色,故C(X)?B2∪B3，C(X)∪C(Y)?B，有10+n≤234,n≤224，因此，當225≤n≤466時，B中的成員不能區分Y中的n個頂點，矛盾。

以下僅考慮當215≤n≤224時的情況。即B1中至多有9個集合不是Y中頂點的色集合，從而每個C(ui)至少同時包含3，4，…，8中的某2種色，i=1,2,…,10。

情形2(a)B2中至少有1個成員是Y中頂點的色集合，可得1,2 ∈C(ui),i=1,2,…,10。

(i)C(ui)恰好 同時包含3，4，…，8中的某2種色，不妨設3,4 ∈C(ui),i=1,2,…,10，則{5,6},{5,7},{5,8},{6,7},{6,8},{7,8}均不是Y中頂點的色集合，從而10+n≤234-6，n≤218。當219≤n≤466時，218個集合不能區分Y中的n個頂點，矛盾。

以下僅考慮當215≤n≤218時的情況。此時{1,5,6},{1,5,7},{1,5,8},{1,6,7},{1,6,8},{1,7,8}至多有3個不是Y中頂點的色集合。如果{1,5,6},{1,5,7},{1,5,8},{1,6,7},{1,6,8},{1,7,8}都是Y中頂點的色集合，則5，6，7，8中至少有3種色同時包含在每個頂點顏色為1的點的色集合,不妨設5,6,7 ∈C(ui),f(ui)=1。此時{2,5,6},{2,5,7},{2,5,8},{2,6,7},{2,6,8},{2,7,8}中至多有3個不是Y中的頂點色集合,可得5，6，7，8中至少有1種色同時包含在每個頂點顏色為2的點的色集合中，設a∈C(ui),f(ui)=2，其中a∈ {5,6,7,8}。若{a}∩{5,6,7}=?，則a=8，從而每個C(ui)只能是以下集合之一:矛盾。

若{a}∩{5,6,7}≠?,則顏色{a}∩{5,6,7}同時包含在每個C(ui)中,與假設矛盾。

如果{1,5,6},{1,5,7},{1,5,8},{1,6,7},{1,6,8},{1,7,8}恰有1個或2個不是Y中頂點的色集合,則5，6，7，8中至少有2種色同時包含在每個頂點顏色為1的點的色集合中,不妨設5,6 ∈C(ui),f(ui)=1；此時中至多有2個不是Y中頂點的色集合,從而5，6，7，8中至少有2種色同時包含在每個頂點顏色為2的點的色集合中,設a,b∈C(ui),f(ui)=2，其中，a

如果{1,5,6},{1,5,7},{1,5,8},{1,6,7},{1,6,8},{1,7,8}中恰有3個不是Y中頂點的色集合,可得5，6，7，8中至少有1種色同時包含在每個頂點顏色為1的點的色集合中,設a∈C(ui),f(ui)=1，其中a∈{5,6,7,8}。此時{2,5,6},{2,5,7},{2,5,8},{2,6,7},{2,6,8},{2,7,8}都是Y中頂點的色集合，可得5，6，7，8中至少有3種色同時包含在每個頂點顏色為2的點的色集合中，不妨設當f(ui)=2時，5,6,7 ∈C(ui)。若{a}∩{5,6,7}=?，則a=8，從而每個C(ui)只能是以下集合之一 :矛盾。

若{a}∩{5,6,7}≠?，從而每個C(ui)同時包含顏色{a}∩{5,6,7}，與假設矛盾。

(ii)C(ui)至少同時包含3，4，…，8中的某3種色，不妨設3,4,5 ∈C(ui)，i=1,2,…,10，從而每個C(ui)只能是以下集合之一:8個集合不能區分X中的10個頂點，矛盾。

情形2(b)B2中成員均不是Y中頂點的色集合。

(i)C(ui)恰好 同時包含3，4，…，8中的某2種色，不妨設3,4 ∈C(ui)，i=1,2,…,10。則{5,6},{5,7},{5,8},{6,7},{6,8},{7,8},{1,2,3},{1,2,4},{1,2,5},{1,2,6},{1,2,7},{1,2,8}均不是X和Y中頂點的色集合，從而10+n≤234－12，有n≤212，212個集合不能區分Y中的n個頂點，矛盾。

(ii)C(ui)恰好同時包含3，4，…，8中的某3種色，不妨設3,4,5 ∈C(ui),i=1,2,…,10。因此{6,7}，{6,8}，{7,8}不是Y中頂點的色集合，且B2中成員均不是X中頂點的色集合。從而10+n≤234－9，n≤215。當216≤n≤466時，215個集合不能區分Y中的n個頂點,矛盾。

以下僅考慮n= 215時的情形。此時均是Y中某頂點的色集合。由于{1,6,7},{1,6,8},{1,7,8}均是Y中頂點的色集合，則每個頂點顏色為1的點的色集合至少同時包含6，7，8中的某2種色，不妨設當f(ui)=1時，6,7 ∈C(ui)；由 于{2,6,7},{2,6,8},{2,7,8}均是Y中頂點的色集合，則每個頂點顏色為2的點的色集合至少同時包含6，7，8中的某2種色，不妨設當f(ui)=2時，a,b∈C(ui)，其中a

(iii)C(ui)恰好同時包含3，4，…，8中的某4種色,不妨設3,4,5,6 ∈C(ui),i=1,2,…,10。因此{7,8}不是Y中頂點色集合，且B2中成員均不是X中頂點的色集合。從而10+n≤234－7,n≤217。當218≤n≤466時,217個集合不能區分Y中的n個頂點,矛盾。

以下僅考慮當215≤n≤217時的情形。此時中存在1個是Y中某頂點vj0的色集合。不妨設f(vj0)=8，所以每個C(ui)包含{1,2},{1,7},{2,7} 3個集合之一。從而每個C(ui)只能是以下集合之一:矛盾。

(iv)C(ui)至少同時包含3，4，…，8中某5種色，不妨設3,4,5,6,7 ∈C(ui),i=1,2,…,10，從 而每個C(ui)只能是集合之一，6個集合不能區分X中的10個頂點，矛盾。

情形3u1,u2,…,u10的顏色當中互不相同的僅有3種，不妨設f(ui)∈{1,2,3},i=1,2,…,10。則當C(vj)是2-子集時，C(vj)不包含顏色1，2 或3，且每個C(vj)都不是{1,2,3}，從而可以作為Y中頂點色集合的{1,2,3,4,5,6,7,8}的子集的數目為，故當229≤n≤466時，228個集合不能區分Y中的n個頂點，矛盾。

下設215≤n≤228。令C=C1∪C2∪C3，C(Y)?C，其中，

C3是{1,2,3,4,5,6,7,8}的4-子集，5-子集，6-子集，7-子集，8-子集和不在C2∪{{1，2，3}}中的3-子集構成的集合。

發現C中包含i成員的有119個，i=1,2,3;C中包含j成員的有123個，j=4,5,6,7,8。因此每個C(ui)至少包含3種色，C(X)∪C(Y)?C∪{{1,2,3}},10+n≤228+1，n≤219。從而當220≤n≤228時，219個集合不能區分Y中的n個頂點，矛盾。

以下僅考慮當215≤n≤219時的情形。此時C1中至多有4個成員不是Y中頂點的色集合,因此4，5，6，7，8中至少有2種色同時包含在每個C(ui)中，不妨 設4,5 ∈C(ui),i= 1,2,…,10。故{1,2,3}不是X中任意一個頂點的色集合，C2中成員均不是X中點的色集合，且至多有4個不是Y中點的色集合，因此可推出1,2,3 ∈C(ui),i=1,2,…,10。從而每個C(ui)只能是以下集合之一 :矛盾。

情形4u1,u2,…,u10的顏色當中互不相同的僅有4種，不妨設f(ui)∈{1,2,3,4},i=1,2,…,10。則當C(vj)是2-子集時,不含顏色1，2，3 或4，且每個C(vj)也都不是{1,2,3},{1,2,4},{1,3,4},{2,3,4},設Y中頂點色集合為D，從而可以作為Y中頂點色集合的{1,2,3,4,5,6,7,8}的子集的數目為當221≤n≤466時，220個集合不能區分Y中的n個頂點,矛盾。

以下僅考慮當215≤n≤220時的情形。發現D中包含i的成員有116個，i=1，2，3，4。D中包含j的成員有119個，j=5,6,7,8。因此每個C(ui)至少包含3種色，故

因此，有10+n≤220+5，可得n≤215。從而當216≤n≤220時，215個集合不能區分Y中的n個頂點，矛盾。

以下僅考慮當n=215時的情形。此時{5,6},均是Y中頂點的色集合，可得5，6，7，8中至少有3種色同時包含在每個C(ui)中，不 妨 設 5,6,7 ∈C(ui),i=1,2,…,10。因此，均不是X中頂點的色集合，從而有10+n≤220,n≤210。210個集合不能區分Y中n個頂點，矛盾。

情形5u1,u2,…,u10的顏色當中互不相同的僅有5種,不妨設f(ui)∈{1,2,3,4,}5 ,i=1,2,…,10。則當C(vj)是2-子集時，只能是{6,7},{6,8},{7,8}，且每個C(vj)也都不是{1,2,3,4,}5的3-子集，4-子集，5-子集，從而可以作為Y中頂點色集合的{1,2,3,4,5,6,7,8}的子集的數目為206個集合不能區分Y中的n個頂點，矛盾。

情形6u1,u2,…,u10的顏色當中互不相同的僅有6種，不妨設f(ui)∈{1,2,3,4,5,}6 ,i=1,2,…,10。則當C(vj)是2-子集時，只能是{7,8}，且每個C(vj)也都不是{1,2,3,4,5,6}的3-子集，4-子集，5-子集，6-子集，從而可以作為Y中頂點色集合的的子集數目為178個集合不能區分Y中的n個頂點，矛盾。

情形7u1,u2,…,u10的顏色當中互不相同的僅有 7種，不 妨 設f(ui)∈{1,2,3,4,5,6,}7 ,i=1,2,…,10。則每個C(vj)不可能是2-子集，每個C(vj)也都不是{1,2,3,4,5,6,}7的3-子集，4-子集，5-子集，6-子集和7-子集，從而可以作為Y中頂點色集合的{1,2,3,4,5,6,7,8}的子集的數目為120個集合不能區分Y中的n個頂點，矛盾。

表1 K10，466 頂點vj(215≤j≤225)及其關聯邊的染色方案Table1 The coloring method of vertex vj and its incident edges ofK10，466 when 215≤j≤225

表2 K10，466 頂點vj(226≤j≤466)及其關聯邊的染色方案Table2 The coloring method of vertex vj and its incident edges of K10，n when 226≤j≤466

因此，K10,n沒有8-VDET染色，且 當215≤n≤466時，χevt(K10,n)≥9。

下面給出K10,n的一個9-VDET 染色。

首先確定f466。X中頂點u1,u2,…,u10的色集合分別為

頂點u1,u2,…,u10的顏色分別為1,2,1,2,1,2,2,2,1,2。

將X∪{v1,v2,}v3,…,v214所導出的K10,466的子圖按照引理3 給出的8-VDET 染色f214進行染色，然后染其他的頂點和關聯邊。

將vj(215≤j≤225)和它的關聯邊按表1的方式進行染色(表1的第1行表示頂點ui(1≤i≤10)的色集合，第2行表示頂點ui(1≤i≤10)的顏色，第3 行的39(3)表示頂點v215著色3，頂點v215的色集合為{3,9}，頂點v215的關聯邊u1v215,u2v215,…,u10v215分別著色9,9,9,9,9,9,9,9,9,9，依此類推)。

將頂點vj(226≤j≤466)分別對應色集合{1,2,3,4,5,6,7,8,9}的全體含顏色9的2-子集，3-子集，4-子集，5-子集，6-子集，7-子集，8-子集，但不是{1,2,9}、{3,9}，也不是表1X中任意一個頂點的色集合。頂點vj(226≤j≤466)和它的關聯邊u1vj,u2vj,…,u10vj的具體染色方案見表2。當215≤j≤466時，K10,466的9-VDET 染 色f466在由X∪{v1,v2,…vj}所導出的子圖上的限制顯然是K10,j的9-VDET 染色fj。

2 結 語

先利用反證法和分析法得到了當215≤n≤466時，用8種顏色不能對K10,n進行點可區別E-全染色。因此，當215≤n≤466時，χevt(K10,n)≥9。然后利用構造染色法，說明了用9種顏色可以對K10,n進行點可區別E-全染色，從而得到其VDET 色數為9。繼續研究了當n≥467時的K10,n的VDET染色。在后續研究中，利用反證法、分析法以及構造染色法，討論并給出了相應的VDET 色數，由于證明過程較長，此證略。