完全二部图K11,n(11≤n≤88)的点可区别E-全染色

汉大玮, 陈祥恩

(西北师范大学 数学与统计学院, 甘肃 兰州 730070)

在图论研究中,图的染色问题具有极其重要的研究意义和应用价值,二部图的一系列点可区别是否正常边染色、点染色以及一系列未必正常全染色等好多问题，图论的研究者仍然追求解决这一系列有趣的难题。

设G是一个简单图。如果给图G的全体顶点以及顶点的边染色,染色规则为对图G的任选2个相邻的顶点用不同的颜色进行染色,任选2个相邻的边用不同的颜色进行染色,边与这条边的关联顶点所染的颜色不一样,这种染色叫做图G的一个正常全染色(简称为全染色)。X表示图G的某一个顶点,C(X)表示顶点X所染颜色及与X顶点相关联的边所染颜色构成的一个集合,把C(X)称为顶点X的色集合。本文讨论完全二部图的点可区别的一类未必正常全染色。如果给图G的任意相邻顶点着有不同的颜色,且让顶点的每条关联边与关联边的顶点着不相同颜色的一个全染色,叫做图G的一个E-全染色。设G的一个E-全染色f,如果满足条件对∀u,v∈V(G),u≠v,有C(u)≠C(v),则称f为图G的一个点可区别E-全染色,简称为VDET染色。图G的点可区别E-全色数：{k|G存在k-VDET染色}。

文献[1-2]提出了图的点可区别正常边染色等概念,文献[3-6]陈祥恩团队讨论了完全二部图、轮、星、扇、圈和路的点可区别染色；文献[7-8]研究了完全二部图的点可区别E-全染色；文献[9-12]中讨论了完全二部图K2,n、K3,n、K6,n和K7,n的点可区别E-全染色；文献[13-14]讨论了完全图和合成图的点可区别正常边染色；文献[15]中得出了mC4的一般点可区别全染色。本文主要利用反证法和分析法研讨K11,n(11≤n≤88)的点可区别E-全染色，并且利用构造染色法得到K11,n的点可区别E-全染色色数，并得到其最佳染色方案。令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种颜色点可区别染色,用颜色1,2,3,4,5分别染色，下面利用结构分析法,则只可分为以下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种颜色进行点可区别E-全染色,那么当11≤n≤28时,有≥6。下面用构造染色法给出K11,n6种颜色的点可区别E-全染色最优染色方案。

表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的关联边u1v1,u2v1,…u11v1分别用4,4,4,4,4,4,4,4,4,4,4染色,以下如此类推)。当11≤n≤28时,K11,28的6种颜色的点可区别E-全染色f28,在由X∪{v1,v2,…,vj}中显然是K11,j的6种颜色的点可区别E-全染色fj所导出的子图所限制的。

表1 K11,28顶点vj(11≤j≤28)关联边的染色方案

(续表1)

定理2 当29≤n≤88时,有

证明用反证法证明。假设K11,n可以用6种颜色进行点可区别E-全染色,则用颜色1,2,3,4,5,6去着色，利用结构分析法,则可分为以下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)中出现,不妨设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种色出现在每个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中至少有某一种色同时出现在每个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种颜色同时出现在每个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种色将同时出现在每个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种颜色出现,故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)中出现,不妨设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中至少有某一种色同时出现在每个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)的数目为当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种颜色同时出现,故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种颜色进行点可区别E-全染色,那么当29≤n≤88时,下面利用构造染色法给出K11,n的一个最优7种颜色进行点可区别E-全染色的染色方案。

首先,对f88进行染色,让完全二部图K11,n所导出的由X∪{v1,v2,…,v28}的构成子图按照表1给出的6种颜色进行染色,然后对剩余的顶点以及剩余顶点的关联边去染色,让vj(29≤j≤44)和这些顶点所关联的一些边按照下面表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的关联边u1vj,u2vj,…u11vj,的具体染色方案在表3中列出。当29≤j≤88时,K11,88的7种颜色点可区别E-全染色对f88进行染色，在由X∪{v1,v2…vj}所导出的子图上的限制很明显是完全二部图K11,j的7种颜色点可区别E-全染色fj。

表2 K11,88顶点vj (29≤j≤44)关联边的染色方案

表3 K11,88顶点vj (45≤j≤88)及与顶点相关联边的染色方案

2 结 语

先利用分析法和反证法得到当29≤n≤88的时候,用6种颜色不能对完全二部图K11,n进行点可区别染色。因此,当29≤n≤88时,然后利用构造染色法,得到用7种颜色可以对完全二部图K11,n进行点可区别E-全染色,这样就可以确定出完全二部图K11,n的VDET色数为7。当n≥89时,不能用7种颜色进行染色，将对完全二部图K11,n的点可区别E-全染色色数继续进行研究。在后面的研究中,可能会继续利用本文所用到的方法,对完全二部图K11,n进行讨论并计算出其相对应的点可区别E-全染色色数,但这个证明过程非常长,因此，证明省略。