漢大瑋, 陳祥恩

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 甘肅 蘭州 730070)

在圖論研究中,圖的染色問(wèn)題具有極其重要的研究意義和應(yīng)用價(jià)值,二部圖的一系列點(diǎn)可區(qū)別是否正常邊染色、點(diǎn)染色以及一系列未必正常全染色等好多問(wèn)題，圖論的研究者仍然追求解決這一系列有趣的難題。

設(shè)G是一個(gè)簡(jiǎn)單圖。如果給圖G的全體頂點(diǎn)以及頂點(diǎn)的邊染色,染色規(guī)則為對(duì)圖G的任選2個(gè)相鄰的頂點(diǎn)用不同的顏色進(jìn)行染色,任選2個(gè)相鄰的邊用不同的顏色進(jìn)行染色,邊與這條邊的關(guān)聯(lián)頂點(diǎn)所染的顏色不一樣,這種染色叫做圖G的一個(gè)正常全染色(簡(jiǎn)稱(chēng)為全染色)。X表示圖G的某一個(gè)頂點(diǎn),C(X)表示頂點(diǎn)X所染顏色及與X頂點(diǎn)相關(guān)聯(lián)的邊所染顏色構(gòu)成的一個(gè)集合,把C(X)稱(chēng)為頂點(diǎn)X的色集合。本文討論完全二部圖的點(diǎn)可區(qū)別的一類(lèi)未必正常全染色。如果給圖G的任意相鄰頂點(diǎn)著有不同的顏色,且讓頂點(diǎn)的每條關(guān)聯(lián)邊與關(guān)聯(lián)邊的頂點(diǎn)著不相同顏色的一個(gè)全染色,叫做圖G的一個(gè)E-全染色。設(shè)G的一個(gè)E-全染色f,如果滿(mǎn)足條件對(duì)?u,v∈V(G),u≠v,有C(u)≠C(v),則稱(chēng)f為圖G的一個(gè)點(diǎn)可區(qū)別E-全染色,簡(jiǎn)稱(chēng)為VDET染色。圖G的點(diǎn)可區(qū)別E-全色數(shù)：{k|G存在k-VDET染色}。

文獻(xiàn)[1-2]提出了圖的點(diǎn)可區(qū)別正常邊染色等概念,文獻(xiàn)[3-6]陳祥恩團(tuán)隊(duì)討論了完全二部圖、輪、星、扇、圈和路的點(diǎn)可區(qū)別染色；文獻(xiàn)[7-8]研究了完全二部圖的點(diǎn)可區(qū)別E-全染色；文獻(xiàn)[9-12]中討論了完全二部圖K2,n、K3,n、K6,n和K7,n的點(diǎn)可區(qū)別E-全染色；文獻(xiàn)[13-14]討論了完全圖和合成圖的點(diǎn)可區(qū)別正常邊染色；文獻(xiàn)[15]中得出了mC4的一般點(diǎn)可區(qū)別全染色。本文主要利用反證法和分析法研討K11,n(11≤n≤88)的點(diǎn)可區(qū)別E-全染色，并且利用構(gòu)造染色法得到K11,n的點(diǎn)可區(qū)別E-全染色色數(shù)，并得到其最佳染色方案。令V(K11,n)=X∪Y，E(K11,n)={uivj：1≤i≤11，1≤j≤n}，其中X={u1，u2，…，u11}，Y={v1，v2，…，vn}。

1 主要定理及證明過(guò)程

定理1當(dāng)11≤n≤28時(shí),

證明用反證法證。先假設(shè)完全二部圖K11,n可以用5種顏色點(diǎn)可區(qū)別染色,用顏色1,2,3,4,5分別染色，下面利用結(jié)構(gòu)分析法,則只可分為以下4種情況進(jìn)行討論。

當(dāng)n=11時(shí),A1中的2-子集起碼有6個(gè)集合屬于C(Y),因此，在所染2,3,4,5的顏色中至少有某3種顏色包含在每個(gè)C(ui)中,不妨設(shè)2,3,4∈C(ui)(i=1,2,…,11),則C(X)?{{1,2,3,4},{1,2,3,4,5}},2個(gè)集合不能給X中的11個(gè)頂點(diǎn)染色,矛盾。

B1={{3,4},{3,5},{4,5}}；B2={{1,2,3},{1,2,4},{1,2,5}}；B3={{1,3,4},{1,3,5},{1,4,5},{2,3,4},{2,3,5},{2,4,5},{3,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,3,4,5},{2,3,4,5},{1,2,3,4,5}}。

下面將情形2分以下2種情況進(jìn)行討論:

情形2.1.C(Y)?B2,不妨設(shè)為{1,2,3},由{1,2,3}是Y中頂點(diǎn)的色集合,可得1,2∈C(ui)(i=1,2,…,11),則C(X)?{{1,2},{1,2,3},{1,2,4},{1,2,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,2,3,4,5}},8個(gè)集合不能給X中的11個(gè)頂點(diǎn)去染色,矛盾。

情形2.2.C(Y)B2,以下僅考慮當(dāng)11≤n≤16時(shí)的情形。這時(shí),在B1∪B3中至多有5個(gè)集合不屬于C(Y)，下面分為2種情況進(jìn)行討論：

情形2.2.1.C(Y)?B1,不妨設(shè)為{3,4},可得3∈C(ui)或4∈C(ui) (i=1,2,…,11)。不妨設(shè)前者成立,此時(shí)在B3中至多有5個(gè)集合不在Y中,設(shè)為C(Y){A1,A2,A3,A4,A5},則C(X)?{{1,3},{2,3},{1,2,3}},8個(gè)集合不能給X中的11個(gè)頂點(diǎn)去著色,矛盾。

情形2.2.2.C(Y)B1,以下只需討論11≤n≤13的情形,在B3中最多也就有2個(gè)集合不屬于C(Y),不妨設(shè)為B1,B2,因此，需要包含1或2的2-子集至少有6個(gè)集合屬于C(X),才能夠給X中的11個(gè)頂點(diǎn)分別著色。

(1){1,2}∈C(X),設(shè)C(ui0)={1,2},可得：1∈C(ui)或2∈C(ui)(i=1,2,…,11)。不妨設(shè)前者成立,從而每個(gè)C(vj)只能是以下集合之一：{1,3,4},{1,3,5},{1,4,5},{1,2,3,4},{1,2,3,5},{1,2,4,5},{1,2,3,4,5},7個(gè)集合不能給Y中的n個(gè)頂點(diǎn)染色,矛盾。

(2)C(X){1,2},則C(X)?{{1,3},{1,4},{1,5},{2,3},{2,4},{2,5}},可得：3,4,5中的3種色全都包含在每個(gè)C(vj)中,不妨設(shè)3,4,5∈C(vj)(j=1,2,…,n)。從而C(Y)?{{1,3,4,5},{2,3,4,5},{1,2,3,4,5}},3個(gè)集合不能給Y中的n個(gè)頂點(diǎn)分別著色,矛盾。

以下分2種子情形討論：

情形3.1.C(Y)?{{4,5}},則C2∪C3中至多有5個(gè)集合屬于C(Y),設(shè)C(Y)?{C1,C2,C3,C4,C5}。由{4,5}∈C(Y),可得4∈C(ui)或5∈C(ui)(i=1,2,…,11)。不妨設(shè)后者成立,由于C(ui)≠C(vj),從而C(X)?{C1,C2,C3,C4,C5,{1,5},{2,5},{3,5}},矛盾。

情形3.2.C(Y){{4,5}},則C2∪C3中至多有4個(gè)集合不屬于C(Y),設(shè)C(Y){D1,D2,D3,D4},且C2中至少有一個(gè)集合屬于C(Y),不妨設(shè){1,2,4}∈C(Y),則{1,2}至少給C(ui)著色2次,剩余的C(ui)包含{1,3}或{2,3}。由于C(ui)≠C(vj),從而C(X)?{{1,2},{1,3},{2,3},{1,2,3},D1,D2,D3,D4},矛盾。

因此,完全二部圖K11,n不能用5種顏色進(jìn)行點(diǎn)可區(qū)別E-全染色,那么當(dāng)11≤n≤28時(shí),有≥6。下面用構(gòu)造染色法給出K11,n6種顏色的點(diǎn)可區(qū)別E-全染色最優(yōu)染色方案。

表1列出了f28(表1的第一行代表X中11個(gè)頂點(diǎn)ui(1≤i≤11)的色集合,其中-26表示頂點(diǎn)不用顏色2和6著色,第二行代表X中11個(gè)頂點(diǎn)ui(1≤i≤11)所染的顏色,其中1表示頂點(diǎn)用1著色，第三行34(3)表示用3染頂點(diǎn)v1,v1的關(guān)聯(lián)邊u1v1,u2v1,…u11v1分別用4,4,4,4,4,4,4,4,4,4,4染色,以下如此類(lèi)推)。當(dāng)11≤n≤28時(shí),K11,28的6種顏色的點(diǎn)可區(qū)別E-全染色f28,在由X∪{v1,v2,…,vj}中顯然是K11,j的6種顏色的點(diǎn)可區(qū)別E-全染色fj所導(dǎo)出的子圖所限制的。

表1 K11,28頂點(diǎn)vj(11≤j≤28)關(guān)聯(lián)邊的染色方案

(續(xù)表1)

定理2 當(dāng)29≤n≤88時(shí),有

證明用反證法證明。假設(shè)K11,n可以用6種顏色進(jìn)行點(diǎn)可區(qū)別E-全染色,則用顏色1,2,3,4,5,6去著色，利用結(jié)構(gòu)分析法,則可分為以下5種情形進(jìn)行探討。

由上面分類(lèi)可以得到,在B中有26個(gè)包含1，2的集合,在B中有29個(gè)包含3,4,5,6的子集合。這樣,每個(gè)C(ui)至少有3種顏色才能進(jìn)行正常染色,故C(X)?B2∪B3,C(X)∪C(Y)?B,有11+n≤48,可得n≤37。因此，當(dāng)38≤n≤48時(shí),矛盾。以下只需對(duì)29≤n≤37時(shí)的情形進(jìn)行討論。

情形2.1.C(Y)?B2,因此,1,2∈C(ui)(i=1,2,…,11),則C(Y)B1。否則,假設(shè)C(Y)?B1,則3,4,5,6中至少有一種顏色在每個(gè)C(ui)中出現(xiàn),不妨設(shè)3∈C(ui)(i=1,2,…,11),從而1,2,3∈C(ui)(i=1,2,…,11),則C(X)?{{1,2,3},{1,2,3,4},{1,2,3,5},{1,2,3,6},{1,2,3,4,5},{1,2,3,4,6},{1,2,3,5,6},{1,2,3,4,5,6}},矛盾。因?yàn)锽1中的集合均不屬于C(X)和C(Y),且42≤11+n≤48,所以當(dāng)31≤n≤37時(shí),42個(gè)集合不能給X和Y中的(11+n)個(gè)頂點(diǎn)著色,矛盾。因此，只需考慮當(dāng)29≤n≤30時(shí)的情形,當(dāng)29≤n≤30時(shí),B2中至多有一個(gè)集合不屬于C(Y)。

情形2.1.1.C(X)?B2,不妨設(shè){1,2,3}是X中點(diǎn)的色集合,由于{4,5,6}為Y中頂點(diǎn)色集合,且{1,2,3}∩{4,5,6}=?,矛盾。

情形2.1.2.C(X)B2,則C(Y)?B2,又{3,4,5},{3,4,6},{4,5,6},{3,4,5,6}∈C(Y),故顏色3,4,5,6中的至少某2種色出現(xiàn)在每個(gè)C(ui)中,從而C(X)?{{1,2,3,4},{1,2,3,5},{1,2,3,6},{1,2,4,5},{1,2,4,6},{1,2,5,6},{1,2,3,4,5},{1,2,3,4,6},{1,2,3,5,6},{1,2,4,5,6},{1,2,3,4,5,6}}。不妨設(shè)C(ui)={1,2,3,4},f(ui0)=1,由于{1,5,6}∈C(Y),則不能同時(shí)正常染色,矛盾。即{1,2,3,4}?C(X),10個(gè)集合不能給X中的11個(gè)頂點(diǎn)進(jìn)行染色,矛盾。

情形2.2.C(Y)B2。

情形2.2.1.C(X)?B2,不妨設(shè)C(ui0)={1,2,3},f(ui0)=1,則C(vj)包含顏色2或3,故C(Y){{4,5},{4,6},{5,6},{1,4,5},{1,4,6},{1,5,6},{4,5,6},{1,4,5,6}},且C(X){{4,5},{4,6},{5,6},{4,5,6}},則11+n≤48-4,有n≤33。當(dāng)34≤n≤37時(shí),矛盾。以下只考慮29≤n≤33時(shí)的情形。

(1)C(Y)?{{3,4},{3,5},{3,6}},不妨設(shè)C(vj0)={3,4},f(vj0)=4,則C(ui)包含顏色3,那么C(X){{1,2,4},{1,2,5},{1,2,6},{1,4,5},{1,4,6},{1,5,6}},從而11+n≤48-4-6,n≤27,矛盾。

(2)C(Y){{3,4},{3,5},{3,6}},則11+n≤48-4-3,n≤30,當(dāng)31≤n≤37時(shí),矛盾。以下僅考慮29≤n≤30時(shí)的情形。此時(shí),C(X){{1,2,5},{1,2,6},{2,5,6}},從而11+n≤48-7-3,n≤27,矛盾。

情形2.2.2.C(X)B2,此時(shí),C(X)∪C(Y)?B1∪B3,有11+n≤38+6,n≤33。因此，當(dāng)34≤n≤37時(shí),矛盾。以下僅考慮29≤n≤33時(shí)的情形。此時(shí)B1中至少有2個(gè)集合屬于C(Y)。

(1)B1中恰有2個(gè)或3個(gè)集合屬于C(Y),因此，在顏色3,4,5,6中至少有某一種色同時(shí)出現(xiàn)在每個(gè)C(ui)中,不妨設(shè)3∈C(ui),(i=1,2,…,11)。則C(X){{1,4,5},{1,4,6},{1,5,6},{2,4,5},{2,4,6},{2,5,6}}。由C(Y)?{{1,4,5},{1,4,6},{1,5,6}},可得包含顏色2的C(X) 至少包含4,5,6中的某2種共同的顏色,設(shè)對(duì)每個(gè)滿(mǎn)足f(uj)=2的uj都有a,b∈C(uj),這里a

(2)B1中恰有4個(gè)或5個(gè)集合屬于C(Y),則在顏色3,4,5,6中至少有某2種顏色同時(shí)出現(xiàn)在每個(gè)C(ui)中,不妨設(shè)3,4∈C(ui),(i=1,2,…,11)。則{1,5,6},{2,5,6},{1,2,5,6}?C(X)且至少有1個(gè)集合屬于C(Y),設(shè)C(vj0)={1,2,5,6},f(vj0)=6,則C(ui)包含{1,2},{1,5}或{2,5}(i=1,2,…,11),因此，C(X)?{{1,3,4,5},{2,3,4,5},{1,2,3,4},{1,3,4,5,6},{2,3,4,5,6},{1,2,3,4,5},{1,2,3,4,6},{1,2,3,4,5,6}},矛盾。

(3)C(Y)?B1,這樣在顏色3,4,5,6中至少有某3種色將同時(shí)出現(xiàn)在每個(gè)C(ui)中,假設(shè)3,4,5∈C(ui),(i=1,2,…,11)。從而C(X)?{{1,3,4,5},{2,3,4,5},{1,3,4,5,6},{2,3,4,5,6},{1,2,3,4,5},{1,2,3,4,5,6}},矛盾。

由上面的分類(lèi)可以得到在集合C中包含25個(gè)含i的子集合(i=1,2,3),包含28個(gè)含j的子集合(j=4,5,6),因此，每個(gè)C(ui)中至少有3種顏色出現(xiàn),故C(X)?{{1,2,3}}∪C2∪C3,C(X)∪C(Y)?{{1,2,3}}∪C,有11+n≤1+44,可得n≤34,從而當(dāng)35≤n≤88時(shí),矛盾。下面只需探討29≤n≤34時(shí)的情形。

情形3.1.C(X)?{1,2,3},則{4,5},{4,6},{5,6},{4,5,6}均不屬于C(X)和C(Y),那么C(X)∪C(Y)?{{1,2,3}}∪C2∪C3{{4,5,6}},即11+n≤1+9+32-1,n≤30。當(dāng)31≤n≤34時(shí),矛盾。當(dāng)29≤n≤30時(shí),設(shè)C(ui0)={1,2,3},f(ui0)=1,則{1,4,5},{1,4,6},{1,5,6}都不屬于C(Y)但同時(shí)都屬于C(X)。那么C(Y)C2,則C(Y)?C3{1,4,5},{1,4,6},{1,5,6},{4,5,6},有n≤32-4=28,矛盾。

情形3.2.C(X){{1,2,3}},此時(shí)C(X)?C2∪C3,C(X)∪C(Y)?C,有11+n≤44,n≤33。故以下只需對(duì)29≤n≤33時(shí)的情形進(jìn)行探討,這時(shí)C中至多有4個(gè)集合不屬于C(X)和C(Y)。

情形3.2.1.C(Y)?C1。此時(shí)顏色4,5,6中至少有某2種顏色同時(shí)在每個(gè)C(ui)中出現(xiàn),不妨設(shè)4,5∈C(ui),(i=1,2,…,11)。則C(X)C2,此時(shí)C(X)?C3,且C2中至多有4個(gè)集合不屬于C(Y),因此，1,2,3∈C(ui),(i=1,2,…,11),從而C(X)?{{1,2,3,4,5},{1,2,3,4,5,6}},矛盾。

情形3.2.2.C1中恰有一個(gè)或2個(gè)子集合不屬于C(X)和C(Y)。此時(shí)在顏色4,5,6中至少有某一種色同時(shí)出現(xiàn)在每個(gè)C(ui)中,假設(shè)4∈C(ui),(i=1,2,…,11),則C(X){{1,2,5},{1,2,6},{1,3,5},{1,3,6},{2,3,5},{2,3,6}}，且至多有3集合不屬于C(Y),那么由以上可以得到1,2,3∈C(ui),(i=1,2,…,11),則C(X)?{{1,2,3,4},{1,2,3,4,5},{1,2,3,4,6},{1,2,3,4,5,6}},故矛盾。

情形3.2.3.C1中的集合都是X和Y中頂點(diǎn)色集合,假設(shè){4,5,6}是Y中某頂點(diǎn)vj0的色集合,設(shè)f(vj0)=6,可得每個(gè)C(ui)包含顏色4或顏色5,則{1,2,6},{1,3,6},{2,3,6}不屬于C(X),但至多有一個(gè)不屬于C(Y),可得1,2,3∈C(ui),(i=1,2,…,11),則C(X)?{{1,2,3,4},{1,2,3,5},{1,2,3,4,5},{1,2,3,4,6},{1,2,3,5,6},{1,2,3,4,5,6}}。

情形3.2.4.C1C(X)∪C(Y),且C2∪C3中至多有一個(gè)集合不屬于C(X)和C(Y),則下面只需對(duì)29≤n≤30的情形進(jìn)行討論：

(1)C(X)C2,則在C2中至少有8個(gè)集合屬于C(Y),可得1,2,3∈C(ui),(i=1,2,…,11),則C(X)?{{1,2,3,4},{1,2,3,5},{1,2,3,4,5},{1,2,3,4,6},{1,2,3,5,6},{1,2,3,4,5,6}},矛盾。

(2)C(X)?C2,不妨設(shè)C(ui0)={1,2,4},f(ui0)=1,又{3,5,6}為Y中頂點(diǎn)色集合,且{1,2,4}∩{3,5,6}=?,故矛盾。

情形4.u1,u2,u3…,u1111個(gè)頂點(diǎn)所染的顏色中互不相同的僅有4種。不妨設(shè)f(ui)∈{1,2,3,4}(i=1,2,…,11),則當(dāng)C(vj)是2-子集時(shí),不含顏色1,2,3或4,且每個(gè)C(Y){{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}},因此，{1,2,3,4,5,6}的子集可作為C(Y)的數(shù)目為當(dāng)39≤n≤88時(shí),矛盾。下面僅考慮29≤n≤38時(shí)的情形。令D=D1∪D2∪D3,其中,D1={{5,6}}；D2={{1,2,5},{1,2,6},{2,3,5},{2,3,6},{3,4,5},{3,4,6},{1,3,5},{1,3,6},{1,4,6},{2,4,5},{2,4,6}}；D3是{1,2,3,4,5,6}所有子集合中的5-子集、6-子集和除去{1,2,3,4}及不在D2∪{{1,2,3},{1,2,4},{1,3,4},{2,3,4}}中的3-子集，共26個(gè)。

通過(guò)以上分類(lèi)可以得出D中包含i集合的共有22個(gè)(i=1,2,3,4),包含j集合的有28個(gè)(j=5,6),因此，在每個(gè)C(ui)中至少有3種顏色同時(shí)出現(xiàn),故C(X)?D2∪D3∪{{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}},C(X)∪C(Y)?D∪{{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}},有11+n≤38+5,即n≤32。從而當(dāng)33≤n≤38時(shí),矛盾。這樣以下只需要討論當(dāng)29≤n≤32時(shí)的情形。

情形4.1.C(Y)?{{5,6}},因此,5∈C(ui)或6∈C(ui),(i=1,2,…,11)。不妨設(shè)后者成立,則C(X){{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}},故C(X)∪C(Y)?D,即11+n≤38,n≤27,27個(gè)集合不能分別給Y中的n個(gè)頂點(diǎn)進(jìn)行染色,矛盾。

情形4.2.C(Y){5,6},則C(X)?{{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}},不妨設(shè)C(ui0)={1,2,3},f(ui0)=1,則每個(gè)C(vj)包含顏色2或顏色3,故C(Y){{1,4,5},{1,4,6},{1,5,6},{4,5,6},{1,4,5,6}}且至少有一個(gè)子集合是X中某頂點(diǎn)ui1的色集合,不妨設(shè)C(ui1)={1,4,5},f(ui1)=1,則每個(gè)C(vj)包含顏色4或顏色5,那么C(Y){{1,2,6},{1,3,6},{2,3,6},{1,2,3,6}},C(Y)?D2∪D3{{1,4,5},{1,4,6},{1,5,6},{4,5,6},{1,4,5,6},{1,2,6},{1,3,6},{2,3,6},{1,2,3,6}},有n≤12+25-9,得n≤28,得出矛盾。

因此,K11,n不能用6種顏色進(jìn)行點(diǎn)可區(qū)別E-全染色,那么當(dāng)29≤n≤88時(shí),下面利用構(gòu)造染色法給出K11,n的一個(gè)最優(yōu)7種顏色進(jìn)行點(diǎn)可區(qū)別E-全染色的染色方案。

首先,對(duì)f88進(jìn)行染色,讓完全二部圖K11,n所導(dǎo)出的由X∪{v1,v2,…,v28}的構(gòu)成子圖按照表1給出的6種顏色進(jìn)行染色,然后對(duì)剩余的頂點(diǎn)以及剩余頂點(diǎn)的關(guān)聯(lián)邊去染色,讓vj(29≤j≤44)和這些頂點(diǎn)所關(guān)聯(lián)的一些邊按照下面表2的方法進(jìn)行染色；讓頂點(diǎn)v44,v45,…,v48分別按照下列色集合的方法進(jìn)行染色：用所有包含顏色7的3-,4-,5-,6-子集,但不包含以下任意一個(gè)集合：{1,2,7},{1,3,4,5,7},{1,3,4,6,7},{2,3,4,6,7},{1,3,4,5,6,7},{2,3,4,5,6,7},{2,3,4,6,7},{1,2,3,4,7},{1,2,3,4,5,7}和{1,2,3,4,6,7}中的任意一個(gè),頂點(diǎn)vj和頂點(diǎn)vj的關(guān)聯(lián)邊u1vj,u2vj,…u11vj,的具體染色方案在表3中列出。當(dāng)29≤j≤88時(shí),K11,88的7種顏色點(diǎn)可區(qū)別E-全染色對(duì)f88進(jìn)行染色，在由X∪{v1,v2…vj}所導(dǎo)出的子圖上的限制很明顯是完全二部圖K11,j的7種顏色點(diǎn)可區(qū)別E-全染色fj。

表2 K11,88頂點(diǎn)vj (29≤j≤44)關(guān)聯(lián)邊的染色方案

表3 K11,88頂點(diǎn)vj (45≤j≤88)及與頂點(diǎn)相關(guān)聯(lián)邊的染色方案

2 結(jié) 語(yǔ)

先利用分析法和反證法得到當(dāng)29≤n≤88的時(shí)候,用6種顏色不能對(duì)完全二部圖K11,n進(jìn)行點(diǎn)可區(qū)別染色。因此,當(dāng)29≤n≤88時(shí),然后利用構(gòu)造染色法,得到用7種顏色可以對(duì)完全二部圖K11,n進(jìn)行點(diǎn)可區(qū)別E-全染色,這樣就可以確定出完全二部圖K11,n的VDET色數(shù)為7。當(dāng)n≥89時(shí),不能用7種顏色進(jìn)行染色，將對(duì)完全二部圖K11,n的點(diǎn)可區(qū)別E-全染色色數(shù)繼續(xù)進(jìn)行研究。在后面的研究中,可能會(huì)繼續(xù)利用本文所用到的方法,對(duì)完全二部圖K11,n進(jìn)行討論并計(jì)算出其相對(duì)應(yīng)的點(diǎn)可區(qū)別E-全染色色數(shù),但這個(gè)證明過(guò)程非常長(zhǎng),因此，證明省略。