完全二部图K6,n(6≤n≤38)的点可区别E-全染色

师志凤, 陈祥恩, 王治文

(1. 西北师范大学 数学与统计学院, 兰州 730070; 2. 宁夏大学 数学统计学院, 银川 750021)

0 引 言

对图G的一个全染色f(正常或未必正常)及图G的任意一个顶点x, 用Cf(x)或在不导致混淆时用C(x)表示顶点x及其关联边的颜色组成的集合. 对于图G的正常全染色f, 若∀u,v∈V(G),u≠v, 有C(u)≠C(v), 则称f为点可区别全染色, 简称VDT染色. 图G的VDT染色所用颜色数目的最小值称为G的点可区别全色数, 记为χvt(G). 文献[1]通过引入图的点可区别全染色, 讨论了完全图、星、完全二部图、轮、扇、路和圈的点可区别全染色, 并提出一个猜想: 若

其中ni为图G度为i的顶点数目(δ≤i≤Δ), 则χvt(G)=μ(G)或μ(G)+1; 文献[2]给出了一个子图及其母图的点可区别全色数之间的关系； 文献[3]和文献[4]分别讨论了mC3和mK4的点可区别全染色.

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个集合不能区分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个集合不能区分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个集合不能区分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}子集的数目为

当12≤n≤38时, 11个集合不能区分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}子集的数目为

当20≤n≤38时, 19个集合不能区分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时, 上述情形必出现, 矛盾.

① 当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个集合不能区分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个集合不能区分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}子集数目为

当17≤n≤38时, 16个集合不能区分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时, 上述情形必出现, 矛盾.

记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}的子集数目为

当12≤n≤38时, 11个集合不能区分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)的色集合(顶点染色).