完全二部圖K9,n(9≤n≤92)的點可區(qū)別E-全染色

楊偉光, 陳祥恩

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

證明: 先證K9,n不存在5-VDET染色. 假設K9,n有1個5-VDET染色f, 所用顏色為1,2,3,4,5, 則需考慮以下4種情形.

當9≤n≤11時, A1中的2-子集至多有2個不是Y中頂點的色集合, 因此, 在2,3,4,5中至少有2種色包含在每個C(ui)中, 不妨設2,3∈C(ui)(i=1,2,…,9), 則每個C(ui)只能是以下集合之一: {1,2,3},{1,2,3,4},{1,2,3,5},{1,2,3,4,5}, 4個集合不能區(qū)分X中的9個頂點, 矛盾.

分兩種子情形討論:

① B2中至少有一個子集是Y中頂點的色集合, 不妨設為{1,2,3}. 由{1,2,3}是Y中頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,9), 則每個C(ui)只能是下面集合之一: {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個集合, 矛盾.

② B2中的子集均不是Y中頂點色集合. 下面僅考慮當9≤n≤16時的情形. 此時, 在B2∪B3中至多有7個集合不是Y中頂點色集合.

(i) B1中至少有一個集合是Y中頂點色集合. 不妨設{3,4}是Y中頂點色集合, 可得3∈C(ui)(i=1,2,…,9)或4∈C(ui)(i=1,2,…,9). 不妨設前者成立, 故{1,2},{1,4},{1,5},{2,4},{2,5},{1,2,4},{1,2,5}不是任意點的色集合, 從而

若{1,2,3}不是任意點的色集合, 則B1中的集合均為Y中頂點色集合, 從而在3,4,5中至少有2種色包含在每個C(ui)中, 不妨設 3,4∈C(ui)(i=1,2,…,9), 則每個C(ui)只能是以下集合之一: {1,3,4},{1,3,4,5},{2,3,4},{2,3,4,5},{1,2,3,4},{1,2,3,4,5}, 6個集合不能區(qū)分X中的9個頂點, 矛盾. 若{4,5}不是任意點的色集合, 則{1,2,3}是X中頂點的色集合, 又{1,4,5}和{2,4,5}是X中頂點的色集合, 且由假設{3,4}是Y中頂點色集合, 故矛盾.

(ii) B1中集合都不是Y中頂點色集合. 此時B3中至多有4個集合不是Y中頂點色集合， 則{1,2}不是任意點的色集合, 故{1,3},{1,4},{1,5}均不是X中任意點的色集合, 或{2,3},{2,4},{2,5}均不是X任意點的色集合. 否則, {1,3},{2,4}是X頂點的色集合, 則3,4∈C(vj). 故{1,3},{2,3}均不是X中點的色集合； {1,4},{2,4}均不是X中點的色集合； {1,5},{2,5}均不是X中點的色集合. 這3個結論至少有兩個是正確的. 假設最多有一個是正確的, 不妨設后兩個錯誤, 則{1,4},{2,5}是X任意點的色集合, 從而4,5∈C(vj), 又B3中同時含4,5的只有7個, 不能區(qū)分n個頂點, 矛盾. 不妨設前兩個結論正確, 則{1,3},{2,3},{1,4},{2,4}均不是任意點的色集合, 從而{3,4},{3,5},{4,5},{1,2}也均不是任意點的色集合, 由于26-8=18, 只能n=9. 若{1,5},{2,5}是X任意點的色集合, 則{2,5}∩{1,3,4}≠?, 故剩下的集合不能區(qū)分K9,9中的18個頂點, 矛盾.

分以下兩種子情形討論.

① {4,5}是Y中頂點色集合, 可得4∈C(ui)(i=1,2,…,9)或5∈C(ui)(i=1,2,…,9), 不妨設前者成立. 若{1,4},{2,4},{3,4}中至少有一個是X某個點的色集合, 則每個C(vj)都包含4, 故{1,2,5},{1,3,5},{2,3,5},{1,2,3,5}不是任意點的色集合, 因此C(X)∪C(Y)?∪C{{1,4},{2,4},{3,4}}, 且不包含{1,2,5},{1,3,5},{2,3,5},{1,2,3,5}, 有9+n≤16+3-4, 可得n≤15, 故15個集合不能區(qū)分X和Y中(9+n)個頂點, 矛盾. 若{1,4},{2,4},{3,4}都不是X中點的色集合, 則C(X)∪C(Y)?C, 只能n=9, 從而{1,2,5},{1,3,5},{2,3,5},{1,2,3,5}是Y中點的色集合, 故1,2,3∈C(ui)(i=1,2,…,9), 可得每個C(ui)只能是下面集合之一: {1,2,3,4},{1,2,3,4,5}, 矛盾.

② {4,5}不是Y中頂點色集合時, 顯然也不是X中任意點色集合, 則C(Y)?C2∪C3.

事實1以下3個結論最多有一個是正確的：

(i) {1,2},{1,3},{2,3}中至少有一個是X中某個頂點的色集合；

(ii) {1,4},{2,4},{3,4}中至少有一個是X中某個頂點的色集合；

(iii) {1,5},{2,5},{3,5}中至少有一個是X中某個頂點的色集合.

當結論(i),(ii)正確時,Y中每個點的色集合同時包含1,4(或2,4或3,4), 但C2∪C3中同時包含1,4的只有7個集合, 矛盾； 當結論(ii),(iii) 正確時,Y中每個點的色集合同時包含4,5(或2,4或3,4), 但C2∪C3中同時包含4,5的只有7個集合, 矛盾； 當結論(i),(iii)正確時, 類似于當結論(i),(ii)正確的情形, 矛盾.

事實2事實1中3個結論都不正確.

設結論(i)正確, 則Y中每個點的色集合同時包含1,2,3中的某一色, 不妨設為1, 則可作為Y中頂點的色集合有10個, 且{1,4},{2,4},{3,4},{1,5},{2,5},{3,5},{4,5}均不是任意點的色集合, 從而在{1,2,4},{1,2,5},{1,3,4},{1,3,5}中至少有3個都是Y中點的色集合, 不妨設前3個是Y中點的色集合, 則可得每個C(ui)同時包含1,2和1,3或1,2,3(i=1,2,…,9), 又可作為Y中頂點的色集合的10個集合中最多有一個不是Y中點的色集合, 記為A, 故每個C(ui)只能是以下集合之一： {1,2},{1,3},{1,2,3},{A}, 矛盾. 設結論(ii)正確, 則Y中每個點的色集合同時包含4, 故{1,2},{1,3},{2,3},{1,5},{2,5},{3,5},{4,5}不是任意點的色集合, 即9+n≤3+10+5, 可得n≤10, 故C(Y)?{{1,2,4},{1,3,4},{2,3,4},{1,4,5},{2,4,5},{3,4,5},{1,2,3,4},{1,2,4,5},{1,3,4,5},{2,3,4,5},{1,2,3,4,5}}, 由于{1,4}是X中某頂點的色集合, 因此{1,2,4},{1,3,4},{2,3,4}不是Y中點的色集合, 即11-3=8, 8個集合不能區(qū)分Y中n個頂點, 矛盾. 當結論(iii)正確時, 可類似得矛盾.

由事實1和事實2可知,C(X)∪C(Y)?C2∪C3∪{{1,2,3}}, 即9+n≤9+6+1, 可得n≤7, 矛盾.

表1 K9,32的6-VDET染色f32

注：A1={1,3,4,5}，A2={2,3,4,5}，A3={1,3,4,6}，A4={2,3,4,6}，A5={1,3,4,5,6}，A6={2,3,4,5,6}，A7={1,2,3,4,5}，A8={1,2,3,4,6}，A9={1,2,3,4,5,6}.

證明: 先證K9,n不存在6-VDET染色. 假設K9,n有1個6-VDET染色f, 所用顏色為1,2,3,4,5,6, 則需考慮以下5種情形.

注意到在B中包含i的集合有26個,i=1,2; 在B中包含j的集合有29個,j=3,4,5,6. 因此, 每個C(vj)至少包含3種顏色, 故C(X)?B2∪B3,C(X)∪C(Y)?B, 有9+n≤48, 可得n≤39. 從而當40≤n≤48時, B中的集合不能區(qū)分X和Y中的(9+n)個頂點, 矛盾. 下面僅考慮當33≤n≤39時的情形.

① B2中至少有一個集合是Y中頂點的色集合. 此時1,2∈C(ui)(i=1,2,…,9). 因此B1中的集合均不是Y中頂點色集合, 否則, 若B1中有一個集合是Y中頂點色集合, 可得3,4,5,6中至少有一種色包含在每個C(ui)中, 不妨設3∈C(ui)(i=1,2,…,9). 從而1,2,3∈C(ui)(i=1,2,…,9), 因此每個C(ui)只能是以下集合之一: {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}, 8個集合不能區(qū)分X中的9個頂點, 矛盾. 故當33≤n≤39時, B2和B3中的集合不能區(qū)分X和Y中的(9+n)個頂點, 矛盾. 由于B1中的集合均不是X和Y中任意點的色集合, 且42≤9+n≤48, 因此當43≤9+n≤48時, 42個集合不能區(qū)分Y中的(9+n)個頂點, 矛盾. 下面僅考慮9+n=42, 即n=33時的情形.

(i) {1,2,3},{1,2,4},{1,2,5},{1,2,6}中至少有一個是X中點的色集合. 由于{4,5,6}為Y中頂點色集合, 且{1,2,3}∩{3,4,5}=?, 故42個集合不能區(qū)分X和Y中的(9+n)個頂點, 矛盾.

(ii) B2中的集合均不是X中任意點的色集合, 則均為Y中頂點的色集合, 又{3,4,5},{3,4,6},{4,5,6},{3,4,5,6}為Y中頂點色集合, 故每個C(ui)至少同時包含3,4,5,6中的某兩種色, 從而每個C(ui)只能是以下集合之一: {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(u1)={1,2,3,4},f(u1)=1, 由于{1,5,6},{2,5,6}為Y中頂點色集合, 且不能同時正常染色, 矛盾； 當C(X)中某點的色集合是{1,2,3,5},{1,2,3,6}時, 同理也可得出矛盾. 即{1,2,3,4},{1,2,3,5},{1,2,3,6}不能作為X中任意點的色集合, 剩下8個集合不能區(qū)分X中的9個頂點, 矛盾.

② B2中的集合都不是Y中頂點色集合.

(i) B2中至少有一個集合是X中頂點色集合. 不妨設C(ui0)={1,2,3},f(ui0)=1, 則每個C(vj)包含顏色2或3, 故{4,5},{4,6},{5,6},{1,4,5},{1,4,6},{1,5,6},{4,5,6},{1,4,5,6}均不是Y中頂點色集合. 若{1,4,5},{1,4,6},{1,5,6},{1,4,5,6}中至少有一個是X中頂點色集合, 不妨設C(ui1)={1,4,5},f(ui1)=1, 則每個C(vj) 包含顏色4或5, 故{3,4},{3,5},{3,6},{1,3,4},{1,3,5},{1,3,6}均不是Y中頂點色集合, 因此n≤48-8-6-4, 即n≤30, 矛盾； 若{1,4,5},{1,4,6},{1,5,6},{1,4,5,6}均不是X中頂點色集合, 則 9+n≤48-8, 即n≤31, 矛盾.

(ii) B2中的集合都不是X中頂點色集合. 此時C(X)∪C(Y)?B1∪B3, 有9+n≤6+38,n≤33. 故下面僅考慮n=33時的情形. 此時B1中的集合全為Y中頂點色集合. 3,4,5,6中至少有3種色同時包含在每個C(ui)中, 不妨設3,4,5∈C(ui)(i=1,2,…，9), 則每個C(ui)只能是以下集合之一: {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集合(i=4,5,6), 因此每個C(ui)至少包含3種色, 故C(X)?C2∪C3∪{{1,2,3}},C(X)∪C(Y)?C∪{{1,2,3}}, 有9+n≤44+1, 可得n≤36. 從而當37≤n≤92時, 45個集合不能區(qū)分X和Y中的(9+n)個頂點, 矛盾. 下面僅考慮33≤n≤36時的情形.

① {1,2,3}是X中頂點色集合， 則{4,5},{4,6},{5,6},{4,5,6}均不是X和Y中任意頂點色集合,C(X)∪C(Y)?{{1,2,3}}∪C2∪C3{{4,5,6}}, 有9+n≤1+9+32-1, 可得n≤32. 矛盾.

② {1,2,3}不是X中頂點色集合, 此時C(X)?C2∪C3,C(X)∪C(Y)?C, 有9+n≤44, 可得n≤35. 故下面僅考慮33≤n≤35時的情形.

(i) C1中的集合都是Y中頂點色集合. 此時4,5,6中至少有2種色同時包含在每個C(ui)中, 不妨設4,5∈C(ui)(i=1,2,…,9), 則C2中的集合都不是X中頂點色集合, 此時C(X)?C3, 且C2中至多有兩個不是Y中頂點色集合, 因此1,2,3∈C(ui)(i=1,2,…,9), 則每個C(ui)只能是以下集合之一: {1,2,3,4,5},{1,2,3,4,5,6}, 矛盾.

(ii) C1中的集合恰有一個不是Y中頂點色集合, 也不是X中頂點色集合. 此時4,5,6中至少有1種色同時包含在每個C(ui)中, 不妨設4∈C(ui)(i=1,2,…,9), 則{1,2,5},{1,2,6},{1,3,5},{1,3,6},{2,3,5},{2,3,6}均不是X中頂點色集合. 由于{1,2,5},{1,2,6},{1,3,5},{1,3,6},{2,3,5},{2,3,6}均為Y中頂點色集合及至多有一個不是Y中頂點色集合, 均可得1,2,3∈C(ui)(i=1,2,…,9), 則每個C(ui)只能是以下4個集合之一: {1,2,3,4,5,6},{1,2,3,4},{1,2,3,4,5},{1,2,3,4,6}, 矛盾.

(iii) C1中的集合恰有2個不是Y中頂點色集合. 此時4,5,6中至少有1種色同時包含在每個C(ui)中, 不妨設4∈C(ui)(i=1,2,…,9), 則{1,2,5},{1,2,6},{1,3,5},{1,3,6},{2,3,5},{2,3,6}均不是X中頂點色集合, 且全為Y中頂點色集合. 可得1,2,3∈C(ui)(i=1,2,…,9), 則每個C(ui)只能是以下4個集合之一: {1,2,3,4,5,6},{1,2,3,4},{1,2,3,4,5},{1,2,3,4,6}, 矛盾.

注意到D中包含22個i集合(i=1,2,3,4), 包含27個j集合(i=5,6). 因此每個C(ui)至少包含3種色, 故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}}, 有9+n≤38+5, 可得n≤34. 從而當35≤n≤38時, 43個集合不能區(qū)分X和Y中的(9+n)個頂點, 矛盾. 下面僅考慮33≤n≤34時的情形.

① {5,6}是Y中某頂點v(j0)的色集合. 此時5∈C(ui)或6∈C(ui)(i=1,2,…，9), 不妨設前者成立. 則{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}均不是X中頂點色集合, 故C(X)∪C(Y)?D, 即9+n≤38, 可得n≤29, 29個集合不能區(qū)分Y中的n個頂點, 矛盾.

② {5,6}不是Y中任一頂點的色集合. 則{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}均是X中頂點色集合, 設C(ui0)={1,2,3},f(ui0)=1, 則每個C(vj)包含顏色2或 3, 故{1,4,5},{1,4,6},{1,5,6},{4,5,6},{1,4,5,6}不是Y中頂點色集合, 由于38-1-5=32, 32個集合不能區(qū)分Y中的n個頂點, 矛盾.

首先確定f92, 令由X∪{v1,v2,…,v32}所導出的K9,92的子圖按表1列出的6-VDET染色f32進行染色; 然后染其他的頂點和關聯(lián)邊. 令vj(33≤j≤45)及其關聯(lián)邊按表2所列方案進行染色.

表2 當33≤j≤45時K9,92的頂點vj及其關聯(lián)邊的染色方案

注：B1={2,3,4,5,6,7}，B2={1,3,4,5,6,7}，B3={1,2,3,4,6,7}，B4={1,2,3,4,5,7}，B5={2,3,4,6,7}，B6={2,3,4,5,7}，B7={1,3,4,6,7}，B8={1,3,4,5,7}，B9={1,2,3,4,5,6,7}.

令頂點v46,v47,…,v92分別對應下列集合: 含顏色7的3-子集、 4-子集、 5-子集、 6-子集, 但不是{1,2,7},{2,3,4,5,6,7},{1,3,4,5,6,7},{1,2,3,4,6,7},{1,2,3,4,5,7},{2,3,4,6,7},{2,3,4,5,7},{1,3,4,6,7},{1,3,4,5,7},{1,2,3,4,5,6,7}中的任意一個集合. 頂點vj(46≤j≤92)及其關聯(lián)邊的染色方案列于表3. 當33≤j≤91時,K9,92的7-VDET染色f92在由X∪{v1,v2,…,vj}所導出的子圖上的限制是K9,j的7-VDET染色fj.

表3 當46≤j≤92時K9,92的頂點vj及其關聯(lián)邊的染色方案