完全二部圖K6,n(6≤n≤38)的點可區(qū)別E-全染色

師志鳳, 陳祥恩, 王治文

(1. 西北師范大學 數(shù)學與統(tǒng)計學院, 蘭州 730070; 2. 寧夏大學 數(shù)學統(tǒng)計學院, 銀川 750021)

0 引 言

對圖G的一個全染色f(正?；蛭幢卣?及圖G的任意一個頂點x, 用Cf(x)或在不導致混淆時用C(x)表示頂點x及其關聯(lián)邊的顏色組成的集合. 對于圖G的正常全染色f, 若?u,v∈V(G),u≠v, 有C(u)≠C(v), 則稱f為點可區(qū)別全染色, 簡稱VDT染色. 圖G的VDT染色所用顏色數(shù)目的最小值稱為G的點可區(qū)別全色數(shù), 記為χvt(G). 文獻[1]通過引入圖的點可區(qū)別全染色, 討論了完全圖、星、完全二部圖、輪、扇、路和圈的點可區(qū)別全染色, 并提出一個猜想: 若

其中ni為圖G度為i的頂點數(shù)目(δ≤i≤Δ), 則χvt(G)=μ(G)或μ(G)+1; 文獻[2]給出了一個子圖及其母圖的點可區(qū)別全色數(shù)之間的關系； 文獻[3]和文獻[4]分別討論了mC3和mK4的點可區(qū)別全染色.

V(K6,n)=X∪Y,E(K6,n)={uivj: 1≤i≤6, 1≤j≤n},

其中:X={u1,u2,…,u6};Y={v1,v2,…,vn}.

1 主要結果

證明: 先證K6,n沒有4-VDET染色, 再給出K6,n的一個5-VDET染色. 假設K6,n有4-VDET染色f, 所用顏色為1,2,3,4, 則有以下3種情形.

情形1)u1,…,u6的顏色相同. 不妨設f(ui)=1(i=1,2,…,6), 則每個C(vj)都不含顏色1, 且每個C(vj)是{2,3},{2,4},{3,4},{2,3,4}之一. 當6≤n≤10時, 4個集合不能區(qū)分Y中的n個頂點, 矛盾.

情形2)u1,…,u6中互不相同的顏色僅有2種. 不妨設f(ui)∈{1,2}(i=1,2,…,6), 則當每個C(vj)是2-子集時,C(vj)不包含顏色1或2, 從而每個C(vj)是以下集合之一: {3,4},{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}. 當7≤n≤10時, 6個集合不能區(qū)分Y中的n個頂點, 矛盾. 當n=6時, 上述6個集合均為Y中頂點的色集合, 由{1,2,3}是Y中某頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 又由于C(ui)≠C(vj), 則每個C(ui)只能是{1,2}, 矛盾.

情形3)u1,…,u6中互不相同的顏色僅有3種. 不妨設f(ui)∈{1,2,3}(i=1,2,…,6), 則每個點vj著色4, 且當C(vj)是2-子集時, 其不包含顏色1,2或3, 且每個C(vj)也不是{1,2,3}. 從而每個C(vj)是{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}之一. 當6≤n≤10時, 4個集合不能區(qū)分Y中的n個頂點, 矛盾.

證明: 先證K6,n沒有5-VDET染色, 再給出K6,n的一個6-VDET染色. 假設K6,n有一個 5-VDET染色f, 所用顏色為1,2,3,4,5, 則有以下4種情形.

情形1)u1,…,u6中互不相同的顏色僅有1種. 不妨設f(ui)=1(i=1,2,…,6), 則每個C(vj)不包含顏色1, 且可作為Y中頂點色集合的{1,2,3,4,5}子集的數(shù)目為

當12≤n≤38時, 11個集合不能區(qū)分Y中的n個頂點, 矛盾.

令

當n=11時, A1中的2-子集均為Y中頂點的色集合, 可得在2,3,4,5中存在2種色, 都包含在每個C(ui)中, 不妨設2,3∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,2,3},{1,2,3,4},{1,2,3,5},{1,2,3,4,5}, 矛盾.

情形2)u1,…,u6中互不相同的顏色僅有2種. 不妨設f(ui)∈{1,2}(i=1,2,…,6), 則當每個C(vj)是2-子集時,C(vj)不包含顏色1或2, 從而可作為Y中頂點色集合的{1,2,3,4,5}子集的數(shù)目為

當20≤n≤38時, 19個集合不能區(qū)分Y中的n個頂點, 矛盾.

令

如果B1中的一個子集和B2中的一個子集均為Y中頂點的色集合, 不妨設為{3,4}和{1,2,3}. 由{3,4}是Y中頂點的色集合, 可得3∈C(ui)(i=1,2,…,6)或4∈C(ui)(i=1,2,…,6), 不妨設前者成立. 由{1,2,3}是Y中頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,2,3},{1,2,3,4},{1,2,3,5},{1,2,3,4,5}, 矛盾. 當17≤n≤19時, 上述情形必出現(xiàn), 矛盾.

① 當n=16時, B1∪B2∪B3中存在3個集合不是Y中頂點的色集合.

若B1中的3個子集都不是Y中頂點的色集合, 則B2∪B3中子集恰好是Y中全體頂點的色集合. 由{1,2,3}是Y中某個頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 由于C(ui)≠C(vj), 則每個C(ui)只能是{1,2}, 矛盾.

若B2中3個子集都不是Y中頂點的色集合, 則B1∪B3中子集恰好是Y中全體頂點的色集合. 由B1中所有的2-子集均為Y中頂點的色集合, 可知在3,4,5中存在2種色, 都包含在每個C(ui)中, 不妨設3,4∈C(ui)(i=1,2,…,6), 則每個C(ui)?{1,3,4},{2,3,4}, 即C(ui)∈B3. 由于C(ui)≠C(vj), 矛盾.

② 當n=15時, B1∪B2∪B3中存在4個集合不是Y中頂點的色集合.

若B1中的3個子集和B2∪B3中的1個子集(記為A1)都不是Y中頂點的色集合, 則B2中至少有1個子集是Y中某個頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 又由于C(ui)≠C(vj), 則每個C(ui)只能是{1,2},A1之一, 矛盾.

若B2中的3個子集和B1∪B3中的1個子集(記為A2)都不是Y中頂點的色集合, 則B1中至少有1個2-子集是Y中某個頂點的色集合, 可知每個C(ui)同時包含3,4,5中的一種色, 不妨設3∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,3},{2,3},{1,2,3},A2, 矛盾.

③ 當n=14時, B1∪B2∪B3中存在5個集合不是Y中頂點的色集合.

若B1中的3個子集和B2∪B3中的2個子集(記為B1,B2)都不是Y中頂點的色集合, 則B2中至少有1個子集是Y中某個頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 由于C(ui)≠C(vj), 則每個C(ui)只能是{1,2},B1,B2之一, 矛盾.

若B2中的3個子集和B1∪B3中的兩個子集(記為B3,B4)都不是Y中頂點的色集合, 則B1中至少有1個2-子集是Y中某個頂點的色集合, 可得每個C(ui)同時包含3,4,5中的某一種色, 不妨設3∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,3},{2,3},{1,2,3},B3,B4, 矛盾.

④ 當n=13時, B1∪B2∪B3中存在6個集合不是Y中頂點的色集合.

若B1中的3個子集和B2中的3個子集都不是Y中頂點的色集合, 則B3中的子集均為Y中頂點的色集合. 由{1,3,4}和{2,3,4}是Y中頂點的色集合, 可得至少2個C(ui)包含顏色{1,2}, 且其他C(ui)包含顏色{1,3}或{1,4}或{2,3}或{2,4}. 因為B3有3個子集不包含顏色3或4, 則每個C(ui)不是2-子集, 故每個C(ui)至少包含3種色, 即C(ui)∈B2∪B3. 由于C(ui)≠C(vj), 則每個C(ui)只能是{1,2,3},{1,2,4}之一, 矛盾.

若B1中的3個子集和B2∪B3中的3個子集(記為C1,C2,C3)都不是Y中頂點的色集合, 且B2中至多有2個子集不是Y中頂點的色集合, 則B2中至少有1個子集是Y中某個頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 從而每個C(ui)只能是{1,2},C1,C2,C3之一, 矛盾.

若B2中的3個子集和B3中的3個子集(記為D1,D2,D3)都不是Y中頂點的色集合, 則B1中的3個2-子集均為Y中頂點的色集合, 可得在3,4,5中存在2種色都包含在每個C(ui)中, 不妨設3,4∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,3,4},{2,3,4},D1,D2,D3, 矛盾.

若B2中的3個子集, B1中的1個子集和B3中的2個子集(記為E1,E2)都不是Y中頂點的色集合, 則B1中至少有1個2-子集是Y中某個頂點的色集合, 可得每個C(ui)同時包含3,4,5中的某一種色, 不妨設3∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,3},{2,3},{1,2,3},E1,E2, 矛盾.

若B2中的3個子集、B1中的2個子集和B3中的1個子集(設為E3)都不是Y中頂點的色集合, 則B1中有1個2-子集是Y中某個頂點的色集合, 可得每個C(ui)同時包含3,4,5中的某一種色, 不妨設3∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,3},{2,3},{1,2,3},E3, 矛盾.

⑤ 當n=12時, B1∪B2∪B3中存在7個集合不是Y中頂點的色集合.

若B1中的3個子集、B2中的3個子集和B3中的1個子集(設為F)都不是Y中頂點的色集合, 則{{1,3,4},{1,3,5},{1,4,5}}和{{2,3,4},{2,3,5},{2,4,5}}中至少各有1個集合是Y中頂點的色集合, 不妨設{1,3,4}和{2,3,4}是Y中頂點的色集合, 可得至少2個C(ui)包含顏色{1,2}, 且其他C(ui)包含顏色{1,3}或{1,4}或{2,3}或{2,4}. 因為B3有3個子集不包含顏色3或4, 則每個C(ui)不是2-子集, 故每個C(ui)至少包含3種色, 即C(ui)∈B2∪B3. 由于C(ui)≠C(vj), 則每個C(ui)只能是{1,2,3},{1,2,4},F之一, 矛盾.

若B1中的3個子集和B2∪B3中的4個子集(設為F1,F2,F3,F4)都不是Y中頂點的色集合, 且B2中至多有2個子集不是Y中頂點的色集合, 則B2中至少有1個子集是Y中某個頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 從而每個C(ui)只能是下列集合之一: {1,2},F1,F2,F3,F4, 矛盾.

若B2中的3個子集、B1中的2個子集和B3中的2個子集(設為H1,H2)都不是Y中頂點的色集合, 則由B1中的1個2-子集是Y中某個頂點的色集合, 可得每個C(ui)同時包含3,4,5中的某一種色, 不妨設3∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,3},{2,3},{1,2,3},H1,H2, 矛盾.

若B2中的3個子集、B1中的1個子集和B3中的3個子集(設為I1,I2,I3)都不是Y中頂點的色集合, 則B1中存在1個2-子集是Y中某個頂點的色集合, 可得每個C(ui)同時包含3,4,5中的某一種色, 不妨設3∈C(ui)(i=1,2,…,6). 因為B3有3個子集不包含顏色3, 若I1,I2,I3恰好是B3中不含顏色3的3個子集{1,4,5},{2,4,5},{1,2,4,5}, 則每個C(ui)只能是{1,3},{2,3},{1,2,3}之一, 矛盾; 若I1,I2,I3中至少有1個集合包含顏色3, 則{1,4,5},{2,4,5},{1,2,4,5}中至少有1個集合是Y中頂點的色集合, 即Y中頂點的色集合不都包含顏色3, 故每個C(ui)不是2-子集, 從而每個C(ui)只能是下列集合之一: {1,2,3},I1,I2,I3, 矛盾.

若B2中的3個子集和B3中的4個子集(設為G1,G2,G3,G4)都不是Y中頂點的色集合, 則B1中的3個2-子集均為Y中頂點的色集合, 可得在3,4,5中存在2種色都包含在每個C(ui)中, 不妨設3,4∈C(ui)(i=1,2,…,6), 則每個C(ui)只能是下列集合之一: {1,3,4},{2,3,4},G1,G2,G3,G4, 由于C(ui)≠C(vj), 從而每個C(ui)只能是G1,G2,G3,G4之一, 矛盾.

⑥ 當n=11時, B1∪B2∪B3中存在8個集合不是Y中頂點的色集合.

若B1中的3個子集、B2中的3個子集和B3中的2個子集都不是Y中頂點的色集合, 則{{1,3,4},{1,3,5},{1,4,5}}和{{2,3,4},{2,3,5},{2,4,5}}中至少各有1個集合是Y中頂點的色集合, 不妨設{1,3,4}和{2,3,4}是Y中頂點的色集合, 可得至少2個C(ui)包含顏色{1,2}, 且其他C(ui)包含顏色{1,3}或{1,4}或{2,3}或{2,4}. 因為B3有3個子集不包含顏色3或4, 則每個C(ui)不是2-子集, 故每個C(ui)至少包含3種色, 即C(ui)∈B2∪B3, 從而

|C(ui)∪C(vj)|=|B3|+2=15,

由于15個集合不能區(qū)分X∪Y中的6+n=17個頂點, 故矛盾.

若B1中的3個子集、B2中的2個子集(不妨設為{1,2,3},{1,2,4})和B3中的3個子集(設為J1,J2,J3)都不是Y中頂點的色集合. 由{1,2,5}是Y中頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 因為B3有5個子集不包含顏色1或2, 則每個C(ui)不是{1,2}, 故每個C(ui)至少包含3種色, 從而每個C(ui)只能是下列集合之一: {1,2,3},{1,2,4},J1,J2,J3, 矛盾.

若B1中的3個子集、B2中的1個子集(不妨設為{1,2,3})和B3中的4個子集(設為K1,K2,K3,K4)都不是Y中頂點的色集合. 由{1,2,4}是Y中頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6), 因為B3有5個子集不包含顏色1或2, 則每個C(ui)不是{1,2}, 故每個C(ui)至少包含3種色, 從而每個C(ui)只能是下列集合之一: {1,2,3},K1,K2,K3,K4, 矛盾.

若B1中的3個子集和B3中的5個子集(設為L1,L2,L3,L4,L5)都不是Y中頂點的色集合, 則B2中的子集均為Y中頂點的色集合, 可得1,2∈C(ui)(i=1,2,…,6). 因為B3有5個子集不包含顏色1或2, 若Li(i=1,2,3,4,5)恰好是B3中不含顏色1或不含顏色2的5個子集, 則每個C(ui)只能是{1,2}, 矛盾; 否則, 每個C(ui)不是{1,2}, 故每個C(ui)至少包含3種色, 從而每個C(ui)只能是下列集合之一: {1,2,3,4},{1,2,3,5},{1,2,4,5},{1,2,3,4,5}, 矛盾.

若B2中的3個子集、B1中的2個子集和B3中的3個子集(設為L1,L2,L3)都不是Y中頂點的色集合, 則由B1中的1個2-子集是Y中某個頂點的色集合, 可得每個C(ui)同時包含3,4,5中的某一種色, 不妨設3∈C(ui)(i=1,2,…,6), 因為B3有3個子集不包含顏色3, 若L1,L2,L3恰好是B3中不含顏色3的3個子集{1,4,5},{2,4,5},{1,2,4,5}, 則每個C(ui)只能是{1,3},{2,3},{1,2,3}之一, 矛盾; 若L1,L2,L3中至少有1個集合包含顏色3, 則{1,4,5},{2,4,5},{1,2,4,5}中至少有1個集合是Y中頂點的色集合, 即Y中頂點的色集合不都包含顏色3, 則每個C(ui)不是2-子集, 從而每個C(ui)只能是下列集合之一: {1,2,3},L1,L2,L3, 矛盾.

若B2中的3個子集、B1中的1個子集和B3中的4個子集(設為M1,M2,M3,M4)都不是Y中頂點的色集合, 則B1中存在1個2-子集是Y中某個頂點的色集合, 可得每個C(ui)同時包含3,4,5中的某一種色, 不妨設3∈C(ui)(i=1,2,…,6). 因為B3有3個子集不包含顏色3, 若M1,M2,M3,M4中包含B3中不含顏色3的3個子集, 不妨設M1={1,4,5},M2={2,4,5},M3={1,2,4,5}, 則每個C(ui)只能是{1,3},{2,3},{1,2,3},M4之一, 矛盾; 否則, 每個C(ui)至少包含3種色, 從而每個C(ui)只能是下列集合之一: {1,2,3},M1,M2,M3,M4, 矛盾.

若B2中的3個子集和B3中的5個子集都不是Y中頂點的色集合, 則B1中的3個2-子集都是Y中頂點的色集合, 可得在3,4,5中存在2種色都包含在每個C(ui)中, 不妨設3,4∈C(ui)(i=1,2,…,6), 則每個C(ui)?{1,3,4},{2,3,4}, 即C(ui)∈B3, 所以

|C(ui)∪C(vj)|=|B3|+|B1|=16,

由于16個集合不能區(qū)分X∪Y中的6+n=17個頂點, 故矛盾.

情形3)u1,…,u6中互不相同的顏色僅有3種, 不妨設f(ui)∈{1,2,3}(i=1,2,…,6), 則當C(vj)是2-子集時,C(vj)不包含色1,2或3, 且每個C(vj)都不是{1,2,3}, 從而可作為Y中頂點色集合的{1,2,3,4,5}子集數(shù)目為

當17≤n≤38時, 16個集合不能區(qū)分Y中的n個頂點, 矛盾.

令

如果{{1,2,4},{1,2,5}}中的1個子集、{{1,3,4},{1,3,5}}中的1個子集和{{2,3,4},{2,3,5}}中的1個子集都是Y中頂點的色集合, 可得每個C(ui)?{1,2,3}(i=1,2,…,6), 從而每個C(ui)只能是下列集合之一: {1,2,3},{1,2,3,4},{1,2,3,5},{1,2,3,4,5}, 矛盾. 當n=16,15時, 上述情形必出現(xiàn), 矛盾.

記C2中{{1,2,4},{1,2,5}},{{1,3,4},{1,3,5}},{{2,3,4},{2,3,5}}分別為C2中3組集合. 當n=14,13時, C2的3組集合中至少要刪去一組, 不妨設{1,2,4}和{1,2,5}不是Y中頂點色集合, 則{1,3,4}和{2,3,4}都是Y中頂點色集合, 或者{1,3,5}和{2,3,5}都是Y中頂點色集合, 不妨設前者成立, 則每個C(ui)?{1,3}或{2,3}或{1,2,3}. 當{4,5}是Y中頂點色集合時, 可得4∈C(ui)(i=1,2,…,6)或5∈C(ui)(i=1,2,…,6), 不妨設前者成立. 則每個C(ui)?{1,3,4}或{2,3,4}或{1,2,3,4}, 即每個C(ui)∈C2∪C3, 因此至少有3個C(ui)等于Y中頂點色集合, 此時n=14, 矛盾. 當{4,5}不是Y中頂點色集合時, 每個C(ui)?{1,3}或{2,3}或{1,2,3}, 則至少有3個C(ui)都不等于{1,3},{2,3},{1,2,3}中的任意一個, 而這3個C(ui)∈C3∪C2{{1,2,4},{1,2,5}}, 又因為C2∪C3{{1,2,4},{1,2,5}}中的集合都是Y中頂點色集合, 此時n=13, 故矛盾.

當n=12,11時, 在C1∪C2∪C3中至少有4個集合不是Y中頂點色集合. 若C2中的3組集合刪去一組, 不妨設{1,2,4}和{1,2,5}不是Y中頂點色集合, 則{1,3,4}和{2,3,4}都是Y中頂點色集合, 或者{1,3,5}和{2, 3,5}都是Y中頂點色集合, 不妨設前者成立, 則每個C(ui)?{1,3}或{2,3}或{1,2,3}. 當{4,5}是Y中頂點色集合時, 可得4∈C(ui)(i=1,2,…,6)或5∈C(ui)(i=1,2,…,6), 不妨設前者成立. 則每個C(ui)?{1,3,4}或{2,3,4}或{1,2,3,4}, 即每個C(ui)∈C2∪C3, 因此至多有4個C(ui)∈C3, 此時, C3中最多有3個集合不是Y中頂點色集合, 即C3中最多有3個集合可作為這4個ui的色集合, 從而至少有1個C(ui)等于Y中頂點色集合, 矛盾. 當{4,5}不是Y中頂點色集合時, 每個C(ui)?{1,3}或{2,3}或{1,2,3}, 則至少有3個C(ui)都不等于{1,3},{2,3},{1,2,3}中的任意一個, 而這3個C(ui)∈C3∪C2{{1,2,4},{1,2,5}}, 此時, C3中最多有2個集合不是Y中頂點色集合, 即C3中最多有2個集合可作為ui的色集合, 且C2{{1,2,4},{1,2,5}}中的集合都是Y中頂點色集合, 則C3∪C2{{1,2,4},{1,2,5}}中最多有2個集合可作為這3個ui的色集合, 則至少有1個C(ui)等于Y中頂點色集合, 矛盾.

若C2中的3組集合刪去2組, 不妨設{{1,2,4},{1,2,5}}和{{1,3,4},{1,3,5}}都不是Y中頂點色集合, 由{2,3,4}是Y中頂點色集合, 可得至少2個ui?{2,3}. 當{4,5}是Y中頂點色集合時, 可得4∈C(ui)(i=1,2,…,6)或5∈C(ui)(i=1,2,…,6), 不妨設前者成立. 則至少有2個C(ui)?{2,3,4}, 由于{2,3,4}是Y中頂點色集合, 則這2個ui∈C3, 此時, C3中最多有1個集合不是Y中頂點色集合, 即C3中最多有1個集合可作為這2個ui的色集合, 則至少有1個C(ui)等于Y中頂點色集合, 矛盾. 當{4,5}不是Y中頂點色集合時, 此時n=11, C3中的集合都是Y中頂點色集合. 由{2,4,5}是Y中頂點色集合, 可得至少有1個C(ui)?{2,3,4}或{2,3,5}, 不妨設C(u1)?{2,3,4}, 則C(u1)∈{2,3,4}∪C3, 由于{2,3,4}∪C3中的集合都是Y中頂點色集合, 則C(u1)等于Y中頂點色集合, 矛盾.

情形4)u1,…,u6中互不相同的顏色僅有4種, 不妨設f(ui)∈{1,2,3,4}(i=1,2,…,6), 則每個C(vj)都不是2-子集, 且每個C(vj)也都不是{1,2,3},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4}, 從而可作為Y中頂點色集合的{1,2,3,4,5}的子集數(shù)目為

當12≤n≤38時, 11個集合不能區(qū)分Y中的n個頂點, 矛盾.

當n=11時, 上述11個集合恰好是Y中頂點的色集合, 由{1,2,5},{1,3,5},{1,4,5},{2,3,5},{2,4,5}都是Y中頂點色集合, 可得每個C(ui)?{1,2,3,4}, 則每個C(ui)只能是{1,2,3,4},{1,2,3,4,5}之一, 矛盾.

表1 K6,38的6-VDET染色

*表示ui(i=1,2,…,6)的色集合(頂點染色).