完全二部圖K11,n(11≤n≤88)的點可區(qū)別E-全染色

漢大瑋, 陳祥恩

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

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

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

文獻[1-2]提出了圖的點可區(qū)別正常邊染色等概念,文獻[3-6]陳祥恩團隊討論了完全二部圖、輪、星、扇、圈和路的點可區(qū)別染色；文獻[7-8]研究了完全二部圖的點可區(qū)別E-全染色；文獻[9-12]中討論了完全二部圖K2,n、K3,n、K6,n和K7,n的點可區(qū)別E-全染色；文獻[13-14]討論了完全圖和合成圖的點可區(qū)別正常邊染色；文獻[15]中得出了mC4的一般點可區(qū)別全染色。本文主要利用反證法和分析法研討K11,n(11≤n≤88)的點可區(qū)別E-全染色，并且利用構(gòu)造染色法得到K11,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 主要定理及證明過程

定理1當11≤n≤28時,

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

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

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種情況進行討論:

情形2.1.C(Y)?B2,不妨設為{1,2,3},由{1,2,3}是Y中頂點的色集合,可得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個集合不能給X中的11個頂點去染色,矛盾。

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

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

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

(1){1,2}∈C(X),設C(ui0)={1,2},可得：1∈C(ui)或2∈C(ui)(i=1,2,…,11)。不妨設前者成立,從而每個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個集合不能給Y中的n個頂點染色,矛盾。

(2)C(X){1,2},則C(X)?{{1,3},{1,4},{1,5},{2,3},{2,4},{2,5}},可得：3,4,5中的3種色全都包含在每個C(vj)中,不妨設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個集合不能給Y中的n個頂點分別著色,矛盾。

以下分2種子情形討論：

情形3.1.C(Y)?{{4,5}},則C2∪C3中至多有5個集合屬于C(Y),設C(Y)?{C1,C2,C3,C4,C5}。由{4,5}∈C(Y),可得4∈C(ui)或5∈C(ui)(i=1,2,…,11)。不妨設后者成立,由于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個集合不屬于C(Y),設C(Y){D1,D2,D3,D4},且C2中至少有一個集合屬于C(Y),不妨設{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種顏色進行點可區(qū)別E-全染色,那么當11≤n≤28時,有≥6。下面用構(gòu)造染色法給出K11,n6種顏色的點可區(qū)別E-全染色最優(yōu)染色方案。

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

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

(續(xù)表1)

定理2 當29≤n≤88時,有

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

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

情形2.1.C(Y)?B2,因此,1,2∈C(ui)(i=1,2,…,11),則C(Y)B1。否則,假設C(Y)?B1,則3,4,5,6中至少有一種顏色在每個C(ui)中出現(xiàn),不妨設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}},矛盾。因為B1中的集合均不屬于C(X)和C(Y),且42≤11+n≤48,所以當31≤n≤37時,42個集合不能給X和Y中的(11+n)個頂點著色,矛盾。因此，只需考慮當29≤n≤30時的情形,當29≤n≤30時,B2中至多有一個集合不屬于C(Y)。

情形2.1.1.C(X)?B2,不妨設{1,2,3}是X中點的色集合,由于{4,5,6}為Y中頂點色集合,且{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)在每個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}}。不妨設C(ui)={1,2,3,4},f(ui0)=1,由于{1,5,6}∈C(Y),則不能同時正常染色,矛盾。即{1,2,3,4}?C(X),10個集合不能給X中的11個頂點進行染色,矛盾。

情形2.2.C(Y)B2。

情形2.2.1.C(X)?B2,不妨設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。當34≤n≤37時,矛盾。以下只考慮29≤n≤33時的情形。

(1)C(Y)?{{3,4},{3,5},{3,6}},不妨設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,當31≤n≤37時,矛盾。以下僅考慮29≤n≤30時的情形。此時,C(X){{1,2,5},{1,2,6},{2,5,6}},從而11+n≤48-7-3,n≤27,矛盾。

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

(1)B1中恰有2個或3個集合屬于C(Y),因此，在顏色3,4,5,6中至少有某一種色同時出現(xiàn)在每個C(ui)中,不妨設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種共同的顏色,設對每個滿足f(uj)=2的uj都有a,b∈C(uj),這里a

(2)B1中恰有4個或5個集合屬于C(Y),則在顏色3,4,5,6中至少有某2種顏色同時出現(xiàn)在每個C(ui)中,不妨設3,4∈C(ui),(i=1,2,…,11)。則{1,5,6},{2,5,6},{1,2,5,6}?C(X)且至少有1個集合屬于C(Y),設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種色將同時出現(xiàn)在每個C(ui)中,假設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}},矛盾。

由上面的分類可以得到在集合C中包含25個含i的子集合(i=1,2,3),包含28個含j的子集合(j=4,5,6),因此，每個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,從而當35≤n≤88時,矛盾。下面只需探討29≤n≤34時的情形。

情形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。當31≤n≤34時,矛盾。當29≤n≤30時,設C(ui0)={1,2,3},f(ui0)=1,則{1,4,5},{1,4,6},{1,5,6}都不屬于C(Y)但同時都屬于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}},此時C(X)?C2∪C3,C(X)∪C(Y)?C,有11+n≤44,n≤33。故以下只需對29≤n≤33時的情形進行探討,這時C中至多有4個集合不屬于C(X)和C(Y)。

情形3.2.1.C(Y)?C1。此時顏色4,5,6中至少有某2種顏色同時在每個C(ui)中出現(xiàn),不妨設4,5∈C(ui),(i=1,2,…,11)。則C(X)C2,此時C(X)?C3,且C2中至多有4個集合不屬于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中恰有一個或2個子集合不屬于C(X)和C(Y)。此時在顏色4,5,6中至少有某一種色同時出現(xiàn)在每個C(ui)中,假設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中頂點色集合,假設{4,5,6}是Y中某頂點vj0的色集合,設f(vj0)=6,可得每個C(ui)包含顏色4或顏色5,則{1,2,6},{1,3,6},{2,3,6}不屬于C(X),但至多有一個不屬于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中至多有一個集合不屬于C(X)和C(Y),則下面只需對29≤n≤30的情形進行討論：

(1)C(X)C2,則在C2中至少有8個集合屬于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,不妨設C(ui0)={1,2,4},f(ui0)=1,又{3,5,6}為Y中頂點色集合,且{1,2,4}∩{3,5,6}=?,故矛盾。

情形4.u1,u2,u3…,u1111個頂點所染的顏色中互不相同的僅有4種。不妨設f(ui)∈{1,2,3,4}(i=1,2,…,11),則當C(vj)是2-子集時,不含顏色1,2,3或4,且每個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ù)目為當39≤n≤88時,矛盾。下面僅考慮29≤n≤38時的情形。令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個。

通過以上分類可以得出D中包含i集合的共有22個(i=1,2,3,4),包含j集合的有28個(j=5,6),因此，在每個C(ui)中至少有3種顏色同時出現(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。從而當33≤n≤38時,矛盾。這樣以下只需要討論當29≤n≤32時的情形。

情形4.1.C(Y)?{{5,6}},因此,5∈C(ui)或6∈C(ui),(i=1,2,…,11)。不妨設后者成立,則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個集合不能分別給Y中的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}},不妨設C(ui0)={1,2,3},f(ui0)=1,則每個C(vj)包含顏色2或顏色3,故C(Y){{1,4,5},{1,4,6},{1,5,6},{4,5,6},{1,4,5,6}}且至少有一個子集合是X中某頂點ui1的色集合,不妨設C(ui1)={1,4,5},f(ui1)=1,則每個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種顏色進行點可區(qū)別E-全染色,那么當29≤n≤88時,下面利用構(gòu)造染色法給出K11,n的一個最優(yōu)7種顏色進行點可區(qū)別E-全染色的染色方案。

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

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

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

2 結(jié) 語

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