完全二部圖K10，n（215≤n≤466）的點(diǎn)可區(qū)別E-全染色

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

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

0 引言

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

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

引理1[11]當(dāng)10≤n≤90時(shí)，有

引理2[12]當(dāng)91≤n≤214時(shí),有

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

1 主要結(jié)果及證明

定理1當(dāng)215≤n≤466時(shí),有

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

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

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

下設(shè)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-子集構(gòu)成的集合。

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

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

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

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

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

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

如果{1,5,6},{1,5,7},{1,5,8},{1,6,7},{1,6,8},{1,7,8}恰有1個(gè)或2個(gè)不是Y中頂點(diǎn)的色集合,則5，6，7，8中至少有2種色同時(shí)包含在每個(gè)頂點(diǎn)顏色為1的點(diǎn)的色集合中,不妨設(shè)5,6 ∈C(ui),f(ui)=1；此時(shí)中至多有2個(gè)不是Y中頂點(diǎn)的色集合,從而5，6，7，8中至少有2種色同時(shí)包含在每個(gè)頂點(diǎn)顏色為2的點(diǎn)的色集合中,設(shè)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個(gè)不是Y中頂點(diǎn)的色集合,可得5，6，7，8中至少有1種色同時(shí)包含在每個(gè)頂點(diǎn)顏色為1的點(diǎn)的色集合中,設(shè)a∈C(ui),f(ui)=1，其中a∈{5,6,7,8}。此時(shí){2,5,6},{2,5,7},{2,5,8},{2,6,7},{2,6,8},{2,7,8}都是Y中頂點(diǎn)的色集合，可得5，6，7，8中至少有3種色同時(shí)包含在每個(gè)頂點(diǎn)顏色為2的點(diǎn)的色集合中，不妨設(shè)當(dāng)f(ui)=2時(shí)，5,6,7 ∈C(ui)。若{a}∩{5,6,7}=?，則a=8，從而每個(gè)C(ui)只能是以下集合之一 :矛盾。

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

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

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

(i)C(ui)恰好 同時(shí)包含3，4，…，8中的某2種色，不妨設(shè)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中頂點(diǎn)的色集合，從而10+n≤234－12，有n≤212，212個(gè)集合不能區(qū)分Y中的n個(gè)頂點(diǎn)，矛盾。

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

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

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

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

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

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

下設(shè)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-子集構(gòu)成的集合。

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

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

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

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

因此，有10+n≤220+5，可得n≤215。從而當(dāng)216≤n≤220時(shí)，215個(gè)集合不能區(qū)分Y中的n個(gè)頂點(diǎn)，矛盾。

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

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

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

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

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

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

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

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

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

頂點(diǎn)u1,u2,…,u10的顏色分別為1,2,1,2,1,2,2,2,1,2。

將X∪{v1,v2,}v3,…,v214所導(dǎo)出的K10,466的子圖按照引理3 給出的8-VDET 染色f214進(jìn)行染色，然后染其他的頂點(diǎn)和關(guān)聯(lián)邊。

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

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

2 結(jié) 語

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