钻石项链图Nk的点被多重集可区别的E-全染色(2 ≤ k ≤ 165)
E-Total Coloring of Nk Which Is Vertex-Distinguished by Multiple Sets (2 ≤ k ≤ 165)
摘要: 利用反证法和构造具体染色的方法,讨论了钻石项链图Nk的顶点被多重集可区别的E-全染色。给出了钻石项链图Nk的相应染色方案,构造了具体的钻石项链图Nk的点被多重集可区别的E-全染色,其中2 ≤ k ≤ 165。
Abstract: In this paper, by using the method of contradiction and the method of constructing concrete col-oring, we discuss E-total coloring of Nk which is vertex-distinguished by multiple sets. The corre-sponding colorings of Nk are presented, and the E-total chromatic numbers of vertex-distinguished Nk with multiple sets are obtained, which 2 ≤ k ≤ 165.
文章引用:曹静. 钻石项链图Nk的点被多重集可区别的E-全染色(2 ≤ k ≤ 165)[J]. 理论数学, 2023, 13(5): 1492-1507. https://doi.org/10.12677/PM.2023.135152

1. 引言

图的点可区别正常边染色在文献 [1] 中提出的。文献 [2] 给出了完全图和星的合成的点可区别正常边色数。关于无爪3-正则图的研究 [3] [4] 已经有不少,其中在文献 [5] 中探讨了特殊的无爪3-正则图钻石项链图。图的点可区别IE-全染色这一概念在文献 [6] 中被提出。并且点可区别IE-全染色在文献 [7] [8] [9] [10] 中针对完全三部图展开研究。上述文献都是基于图的点被非多重集可区别全染色所做出的工作,而我们在本文中所提出的为图的点被多重集可区别的E-全染色,并给出了钻石项链的染色的方案,构造了具体钻石项链 N k ( 2 k 165 ) 的点被多重集可区别的E-全染色。

v是G的一个顶点,v的度是点关联的边数,若对所有 v V 都有d(v) = k,则称G为k-正则的。任意两个顶点都邻接的图称为完全图,将含n个顶点的完全图记为Kn。特别的,K3称为三角形,K4去掉一个边称作钻石。

对于一个整数k ≥ 2,令Nk表示如下定义的连通的3-正则图,取k个不交的钻石 D 1 , D 2 , , D k V ( D i ) = { a i , b i , c i , d i } a i b i D i 中去掉的边。令Nk是由这k个钻石通过不交的并,并添加边 { a i b i + 1 | i = 1 , 2 , , k 1 } a k b 1 构成的图。将Nk叫做一个k个钻石的钻石项链(图1)。

Figure 1. A diamonds

图1. 一个钻石

图G的VE-全染色是指使得每条关联边与它的端点染以不同的颜色(I条件)的一个VE-全染色。图G的E-全染色是指使得相邻顶点染以不同色(V条件),每条关联边与它的端点染以不同的颜色(I条件)的一个E-全染色。图G使用了k种颜色的VE-全染色叫做图G的k-VE-全染色,图G使用了k种颜色的E-全染色叫做图G的k-E-全染色。若f为图G的E-全染色。对于任意的 x V ( G ) ,用 C ˜ ( x ) 表示点x的色以及与x相关联的边的颜色构成的多重集。称 C ˜ ( x ) 为点x的多重色集合或色集合。显然有 | C ˜ ( x ) | = d G ( x ) + 1 ,其中, d G ( x ) 表示图G中点x的度。若对任意的 u , v V u v ,总有 C ˜ ( u ) C ˜ ( v ) ,则称f是点被多重色集合可区别的。

χ ˜ v t e ( G ) 称为图G的点被多重集可区别的E-全色数, χ ˜ v t v e ( G ) 称为图G的点被多重集可区别的VE-全色数。 χ ˜ v t e ( G ) = min{k|G存在点被多重集可区别的k-E-全染色}。 χ ˜ v t v e ( G ) = min{k|G存在点被多重色集合可区别的k-VE-全染色}。

设图G中存在使用了l种色的点被多重色集合可区别的E-全染色, n i 为i度点的个数, A j 为从l-1种颜色里有重复的取出i + 1种颜色使j只出现1次的组合, j = 1 , 2 , 3 , , l 。其中 | A j | 为从l-1种颜色里有重复的取出i种颜色的组合的个数。

η ˜ ( G ) 表示满足下面两条件对一切使得 δ i Δ i都成立的正整数l的最小值,分为以下两个情形:

情形1 l i + 2。

| A 1 A 2 A 3 A i + 1 | = ( l 1 1 ) ( l + i 2 i ) ( l 1 2 ) ( l + i 4 i 1 ) + ( l 1 3 ) ( l + i 6 i 3 ) + + ( 1 ) i ( l 1 i 1 ) ( l i + 2 2 ) + ( 1 ) i + 1 ( l 1 i + 1 ) ( l i 3 0 ) n i ;

情形2 l i + 1。

| A 1 A 2 A 3 A l 2 | = ( l 1 1 ) ( l + i 2 i ) ( l 1 2 ) ( l + i 4 i 1 ) + ( l 1 3 ) ( l + i 6 i 3 ) + + ( 1 ) l 2 ( l 1 l 3 ) ( i l + 6 i l + 4 ) + ( 1 ) l 1 ( l 1 l 2 ) ( i l + 3 i l + 3 ) n i ;

命题1 χ ˜ v t e ( G ) χ ˜ v t v e ( G ) η ˜ ( G )

2. 准备工作

以下定义十一种剖分:

设Np是一个点被多重集可区别的q-E-全染色fpp阶钻石项链,其q种颜色是 1 , 2 , , q

O1型剖分运算:设ijsht是五种互不相同的颜色, i , j , s , t , h { 1 , 2 , 3 , , q } 。且{i,t,j,j},{j,t,i,i}{i,j,s,t},{i,j,h,t}均不是Np外围圈上的任意点在fp下的色集合,所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h;t] -O1型剖分运算是指将Np按照图2所示的方法变成Np+1的过程。

Figure 2. The color of vertex u is not i, and the color of vertex v is not j

图2. 点u的色不是i,点v的色不是j

O2型剖分运算:设i,j,s,h,t,r是六种互不相同的颜色, i , j , s , h , t , r { 1 , 2 , 3 , , q } 。且{i,r,t,t},{j,r,t,t}{s,r,t,t},{h,r,t,t}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h;r,t]-O2型剖分是指将Np按照图3所示的方法变成Np+1的过程。

Figure 3. The color of vertex u is not i, and the color of vertex v is not j

图3. 点u的色不是i,点v的色不是j

O3型剖分运算:设i,j,s,h,t是五种互不相同的颜色, i , j , s , h , t { 1 , 2 , 3 , , q } 。且{i,t,j,j},{j,t,i,i}{i,j,s,t},{i,j,s,h}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h;t]- O3型剖分是指将Np按照图4所示的方法变成Np+1的过程。

图4. 点u的色不是i,点v的色不是j

O4型剖分运算:设i,j,s,h,r是五种互不相同的颜色, i , j , s , h , r , t { 1 , 2 , 3 , , q } 。且{i,t,j,j},{i,t,r,r},{s,r,i,j},{h,r,i,j}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,s,h;j,r,t]-O4型剖分是指将Np按照图5所示的方法变成Np+1的过程。

图5. O4型剖分运算

O5型剖分运算:设i,j,s,h,是四种互不相同的颜色, i , j , s , h , r , t { 1 , 2 , 3 , , q } 。且{i,t,j,j},{j,t,i,i}{s,r,i,j},{h,r,i,j}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h;r,t]- O5型剖分是指将Np按照图6所示的方法变成Np+1的过程。

O6型剖分运算:设i,j,s,h,是四种互不相同的颜色, i , j , s , h , m , n , r , t { 1 , 2 , 3 , , q } 。且{i,t,r,m},{j,t,r,m}{s,r,m,n},{h,r,m,n}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h;m,n,r,t]- O6型剖分是指将Np按照图7所示的方法变成Np+1的过程。

图6. 点u的色不是i,点v的色不是j

图7. 点u的色不是i,点v的色不是j

S1型剖分运算:设i,j,s,h,m,n,r,t是八种互不相同的颜色 i , j , s , h , m , n , r , t { 1 , 2 , 3 , , q } 。且{i,t,t,t},{i,s,t,t},{i,h,t,t},{i,j,t,t},{j,t,r,r},{r,t,i,i},{m,i,t,r},{n,i,t,r}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h,m,n;r,t]-S1型剖分是指将Np按照图8所示的方法变成Np+2的过程。

Figure 8. The color of vertex u is not i, and the color of vertex v is not r

图8. 点u的色不是i,点v的色不是r

S2型剖分运算:设i,j,s,h,m,n,t是七种互不相同的颜色 i , j , s , h , m , n , t { 1 , 2 , 3 , , q } 。且{i,t,t,t},{s,t,t,t},{h,t,t,t},{i,j,t,t},{m,i,t,t},{j,t,i,i},{n,t,i,i},{m,t,i,i}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h,m,n;t]-S2型剖分是指将Np按照图9所示的方法变成Np+2的过程。

S3型剖分运算:设i,j,s,h,r,t是六种互不相同的颜色 i , j , s , h , r , t { 1 , 2 , 3 , , q } 。且{i,r,r,t},{s,r,r,t},{h,r,r,t},{r,j,t,t},{r,i,t,t},{s,r,t,t},{h,r,t,t},{j,t,r,r}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h;r,t]-S3型剖分是指将Np按照图10所示的方法变成Np+2的过程。

Figure 9. The color of vertex u is not i, and the color of vertex v is not m

图9. 点u的色不是i,点v的色不是m

图10. 点u的色不是i,点v的色不是j

T1型剖分运算:设i,j,s,t是四种互不相同的颜色 i , j , s , t , r { 1 , 2 , 3 , , q } 。且{i,t,j,j},{s,t,j,j},{t,j,j,j},{r,j,t,t}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,r;t]-T1型剖分是指将Np按照图11所示的方法变成Np+1的过程,其中r可以为i

Figure 11. The color of vertex u is not i, and the color of vertex v is not r

图11. 点u的色不是i,点v的色不是r

T2型剖分运算:设i,j,s,h,t是五种互不相同的颜色 i , j , s , h , r , t { 1 , 2 , 3 , , q } 。且{i,t,r,r},{s,r,r,r},{j,t,r,r},{h,r,r,r}均不是Np外围圈上的任意点在fp下的色集合。所谓对Np的染有颜色t的一条边uv实施一次[i,j,s,h;r,t]-T2型剖分是指将Np按照图12所示的方法变成Np+1的过程,其中r可以为t

Figure 12. The color of vertex u is not i, and the color of vertex v is not j

图12. 点u的色不是i,点v的色不是j

3. 主要结论及其证明

定理1 N k ( 2 k 165 ) 的点被多重集可区别的E-全染色

χ ˜ v t e ( N k ) = { 4 , 2 k 5 ; 5 , 6 k 12 ; 6 , 13 k 23 ; 7 , 24 k 42 ; 8 , 43 k 68 9 , 69 k 110 10 , 111 k 165

证明 根据命题1与 N k ( 2 k 165 ) 的性质, N k ( 2 k 165 ) 中3度点有n个,则有

η ˜ ( N k ) = min { l | ( l 1 1 ) ( l + 1 3 ) ( l 1 2 ) ( l 1 2 ) + ( l 1 3 ) ( l 3 1 ) ( l 1 4 ) 4 k } ;

k ( l 1 1 ) ( l + 1 3 ) ( l 1 2 ) ( l 1 2 ) + ( l 1 3 ) ( l 3 1 ) ( l 1 4 ) 4

假设Nk存在点被多重集可区别的l-E-全染色fk { 1 , 2 , , l } ,其中一个钻石Di存在点被多重集可区别的l-E-全染色fk { 1 , 2 , , l } ,不妨设序列:

f D i = ( f k ( b i 1 a i ) f k ( a i ) f k ( c i a i ) f k ( d i a i ) , f k ( a i c i ) f k ( c i ) f k ( c i d i ) f k ( c i b i ) , f k ( a i d i ) f k ( d i ) f k ( c i d i ) f k ( d i b i ) , f k ( c i b i ) f k ( b i ) f k ( d i b i ) f k ( b i a i + 1 ) ) , i = 1 , 2 , , k 1

f k = ( f D 1 ; f D 2 ; ; f D k )

情形1 2 k 5

首先证明当k = 2时, χ ˜ v t e ( N k ) > 3 。(尽管此时 η ˜ ( N k ) = 3 ,但 χ ˜ v t e ( N k ) > 3 。)

假设Nk存在顶点被多重集点可区别染色的3-E-全染色h。若一个4-子集能够成为一个顶点的色集合,必须具备“某一种颜色在该4-子集里仅出现一次”的性质。所以能够成为顶点的色集合的4-子集,只可能是以下9个子集:

{1,1,1,2},{1,1,1,3},{2,2,2,1},{2,2,2,3},{3,3,3,1},{3,3,3,2},{1,2,3,1},{1,2,3,2},{1,2,3,3};

则N2只能为以下模式: h 2 = ( 3132 , 3213 , 2312 , 3123 ; 3231 , 3123 , 1321 , 3213 )

显然 C ( a 1 ) = C ( b 2 ) ,故这两点无法可区别,矛盾。

综上可得, χ ˜ v t e ( N k ) > 3

其次,当 3 k 6 时, η ˜ ( N k ) = 4 ,则由命题1, χ ˜ v t e ( N k ) 4 。但当k = 6时, η ˜ ( N k ) > 4

假设N6存在顶点被多重集点可区别染色的4-E-全染色。将能够成为一个顶点的色集合的25个4-子集分为两类,一类形如iiij,其中i,j = 1,2,3,4且ij共12个,剩余的13个4-子集成为第二类。之后,若一个钻石存在顶点被多重集点可区别染色的4-E-全染色g,这样的g可分为A,B,C,D,E五类模块,其中i,j,s,t为四种不同的颜色,模块分别为:

A类模块由三个一类4-子集,一个二类4-子集组成;则g = (isii,itii,ijii,isir),其中r = tj

B类模块由两个一类4-子集,两类个二类4-子集组成;则g = (ijii,itis,isii,sjir),其中r = si

C类模块由两个一类4-子集,两类个二类4-子集组成;则g = (isii,ijrs,itrs,siss),其中r = si

D类模块由一个一类4-子集,三类个二类4-子集组成;则g = (kthi,hjir,isii,rtim),其中r = si,h = si,r hk = i,j,sm = i,j,skm可以相同。

E类模块由四个二类4-子集组成;

再将这五个模块结合为六个钻石,最后将这六个钻石按照边 b i 1 a i 和边 b i a i + 1 的颜色串成圈(颜色相同的可相邻,反之不可),分为以下几个情形:

情形1.1 包含4个A类模块,2个E类模块

若N6包含4个A类模块,不妨设4个A模块所用的第二类4-子集为{1,1,2,3},{2,2,3,4},{1,3,3,4},{1,3,4,4},且剩余的9个4-子集中的4个4-子集可组合为E模块的色集合 (3213,1341,3144,1243),故剩余{1,2,2,3},{1,1,2,4},{1,2,2,4},{2,3,3,4},{2,3,4,4}其中有4个4-子集组合起来必会成为一个钻石的色集合。

若这个钻石的色集合含{1,1,2,4},令顶点a6的顶点着色为2,a6外接边的颜色为1,则顶点b6的色集合需要颜色2,颜色4,颜色1皆出现一次。但{1,2,2,3}中颜色4不出现,{2,3,3,4}中颜色1不出现。

令顶点a6的顶点着色为4,a6外接边的颜色为1,则顶点c6的色集合只能为{1,3,2,2},故顶点d6的色集合需要出现颜色2两次,但剩余的三个集合都不满足。

令顶点a6的顶点着色为4,a6外接边的颜色为2,则顶点c6的色集合只能为{1,3,2,2},顶点d6着色需满足V条件,并且色集合需要出现颜色1一次,颜色2一次,但剩余的三个集合都不满足。

令顶点a6的顶点着色为2,a6外接边的颜色为4,则顶点c6的色集合只能为{1,4,2,2},顶点d6的色集合只能为{1,3,2,2},故顶点b6的色集合需要出现颜色2两次,但剩余的两个集合都不满足。

故这个钻石的色集合不含{1,1,2,4},因此这个钻石的色集合只能包含{1,2,2,3},{1,2,2,4},{2,3,3,4},{2,3,4,4}。

若这个钻石的色集合含{1,2,2,4},令顶点a6的顶点着色为4,a6外接边的颜色为2,则顶点c6的色集合只能为{1,3,2,2},故顶点d6的色集合需要出现颜色2两次,但剩余的两个集合都不满足。

令顶点a6的顶点着色为1,a6外接边的颜色为2,若顶点c6的色集合为{4,2,3,3},则顶点d6的色集合只能为{2,1,3,2},故顶点b6的色集合需要出现颜色2一次,颜色3一次且满足I条件,但{2,3,4,4}不满足上述条件。若顶点c6的色集合为{4,2,3,4},则g = {2142,4234,2132,4324},因C(a6) = {2142},C(b6) = {4324},但C(a1) = {1311}所以无法串成圈。若顶点c6的色集合为{4243},故顶点d6的色集合需要出现颜色2一次,颜色4一次且满足I条件,但{2,3,3,4},{1,2,2,3}不满足上述条件。

令顶点a6的顶点着色为1,a6外接边的颜色为4,若顶点c6的色集合{2,3,1,2},故顶点d6的色集合需要出现颜色1一次,颜色2一次,但剩余的两个个集合都不满足。若顶点c6的色集合{2,3,2,1},故顶点d6的色集合需要出现颜色2两次,但剩余的两个集合都不满足。若顶点c6的色集合{2,4,3,3},故顶点d6的色集合需要出现颜色2一次,颜色3一次且满足I条件,但剩余的两个集合都不满足。若顶点c6的色集合{2,3,4,4},故顶点d6的色集合需要出现颜色2一次,颜色4一次且满足I条件,但剩余的两个集合都不满足。

令顶点a6的顶点着色为4,a6外接边的颜色为1,若顶点c6的色集合{2,3,1,2},故顶点d6的色集合需要出现颜色1一次,颜色2一次,但剩余的两个集合都不满足。若顶点c6的色集合{2,3,2,1},故顶点d6的色集合需要出现颜色2两次,但剩余的两个集合都不满足。若顶点c6的色集合{2,4,3,3},则不满足V条件。若顶点c6的色集合{2,3,4,4},故顶点d6的色集合需要出现颜色2一次,颜色4一次且满足I条件,但剩余的两个集合都不满足。

故在情形1.1中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.2 包含3个A类模块,1个B类模块,1个D类模块,1个E类模块

若N6包含3个A类模块,不妨设3个A模块所用的第一类4-子集为iiij,其中i,j = 1,2,3且i j,第二类4-子集为{1,1,2,3},{2,2,1,3},{1,3,3,2}。

若{4,4,4,1}与{4,4,4,2}与两个第二类4-子集组合为B模块,{4,4,4,3}与三个第二类4-子集组合为D模块。B模块的色集合不妨为{4144,4342,4244,2142},D模块的色集合只能为{4134,3243,4344,3143},E模块的色集合只能为{1412,1243,2142,3422},之后将得到的六个模块串成一个链,但因C(b6) = {3143},但C(a1) = {1311}所以无法串成圈。

若{4,4,4,1}与{4,4,4,3}与两个第二类4-子集组合为B模块,{4,4,4,2}与三个第二类4-子集组合为D模块。B模块的色集合不妨为{3134,3244,4344,4144},D模块的色集合只能为{4124,2342,4244,2142},E模块的色集合只能为{1413,1342,3143,2433},之后将得到的六个模块串成一个链,但因C(b6) = {2142},但C(a1) = {1311}所以无法串成圈。

若{4,4,4,2}与{4,4,4,3}与两个第二类4-子集组合为B模块,{4,4,4,1}与三个第二类4-子集组合为D模块。B模块的色集合不妨为{4244,4143,4344,2342},D模块的色集合只能为{1314,1241,4144,1434},E模块的色集合只能为{2124,2433,4234,3142},之后将得到的六个模块串成一个链,但因C(a6) = {4244},C(b6) = {2342},但C(a1) = {1311}所以无法串成圈。

故在情形1.2中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.3 包含2个A类模块,2个B类模块,1个C类模块,1个E类模块

若N6包含2个A类模块,不妨设2个A模块所用的第一类4-子集为iiij,其中i,j = 1,2且i j,第二类4-子集为{1,1,2,3},{2,2,1,3}。

只能{3,3,3,1}与{3,3,3,2}与两个第二类4-子集组合为一个B1模块,{4,4,4,1}与{4,4,4,2}与两个第二类4-子集组合为一个B2模块,{3,3,3,4}与{4,4,4,3}与两个第二类4-子集组合为C模块。

若C模块的色集合为{3433,1344,2344,4344},B2模块的色集合中的{1,3,4,4},{2,3,4,4}已被使用,无法组合为B2模块的色集合。

若C模块的色集合为{3433,1334,2334,4344},B1模块的色集合中的{1,3,3,4},{2,3,3,4}已被使用,无法组合为B1模块的色集合。

C模块的色集合有且仅有这两种,故在情形1。3中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.4 包含2个A类模块,1个C类模块,3个D类模块

若N6包含2个A类模块,不妨设2个A模块所用的第一类4-子集为iiij,其中i,j = 1,2且i j,第二类4-子集为{1,1,2,3},{2,2,1,3}。{3,3,3,4}与{4,4,4,3}与两个第二类4-子集组合为C模块。{3,3,3,1},{3,3,3,2},{4,4,4,1},{4,4,4,2}从中取三个与三个第二类4-子集组合为D1,D2,D3模块。

若C模块的色集合为{3433,1344,2344,4344},D1模块的色集合为{1431,1233,3133,3431},D2模块的色集合为{2124,2342,4244,2144},D3模块的色集合为{1431,1233,3133,3431}。剩余的第二类4-子集为{1,1,2,4},{2,3,3,4},{1,2,3,4},因{1,1,2,4}中没有颜色3,故只能由{4,4,4,1}与上述三个子集组合。若{1,1,2,4}是a6的色集合,故顶点c6的色集合只能是{1,3,4,2},故顶点b6的色集合需要出现颜色2一次,颜色4一次,但剩余的两个集合都不满足。若{1,1,2,4}是c6的色集合,故顶点a6的色集合只能是{2,3,1,4},故顶点b6的色集合需要出现颜色1一次,颜色4一次,但剩余的两个集合都不满足。

故在情形1.4中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.5 包含2个A类模块,2个B类模块,2个D类模块

若N6包含2个A类模块,不妨设2个A模块所用的第一类4-子集为iiij,其中i,j = 1,2且i j,第二类4-子集为{1,1,2,3},{2,2,1,3}。{3,3,3,1}与{3,3,3,2}与两个第二类4-子集组合为B1模块,{4,4,4,1}与{4,4,4,2}与两个第二类4-子集组合为B2模块,{3,3,3,4},{4,4,4,3}分别与三个第二类4-子集组合为D1,D2模块。

则B1的色集合为{3133,3432,3233,2133},B2的色集合为{4144,4324,4244,2142},余{1,1,2,4},{1,2,4,4},{1,1,3,4},{1,3,3,4},{1,3,4,4},{2,2,3,4},{1,2,3,4}与{3,3,3,4},{4,4,4,3}组合为D1,D2模块,其中{1,1,3,4}因不满足V条件,故无法与其组合。则余下的六个第二类4-子集必能与{3,3,3,4},{4,4,4,3}组合为D1,D2模块。

若{1,3,3,4}与{3,3,3,4}组合为D1模块,则c5的色集合只能是{4,2,3,1},故顶点b6的色集合需要出现颜色1一次,颜色3一次且满足V条件,但剩余的两个集合都不满足。故{1,3,3,4}无法与{3,3,3,4}组合为D1模块。则剩余的3个含颜色“3”的4-子集必可与{3,3,3,4}组合为D1模块。

若{1,3,4,4}与{3,3,3,4}组合为D1模块,则c5的色集合只能是{4,2,3,1},故顶点b6的色集合需要出现颜色1一次,颜色3一次且满足V条件,但剩余的两个集合都不满足。故{1,3,4,4}无法与{3,3,3,4}组合为D1模块。

故在情形1.5中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.6 包含1个A类模块,3个B类模块,1个C类模块,1个D类模块

若N6包含1个A类模块,不妨设1个A模块的色集合{1311,1211,1411,1312}。{2,2,2,1}与{2,2,2,3}与两个第二类4-子集组合为B1模块,{3,3,3,1}与{3,3,3,2}与两个第二类4-子集组合为B2模块,{4,4,4,1}与{4,4,4,2}与两个第二类4-子集组合为B3模块,{3,3,3,4}与{4,4,4,3}与两个第二类4-子集组合为C模块,{2,2,2,4}与三个第二类4-子集组合为D模块。

若C模块的色集合为{3433,3134,3234,4344},则B2模块没有{2,3,3,4}或{1,3,3,4},无法组合。

若C模块的色集合为{3433,3144,3244,4344},则B3模块没有{2,3,4,4}或{1,3,4,4},无法组合。

C模块的色集合有且仅有这两种,故在情形1.6中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.7 包含1个A类模块,2个B类模块,2个C类模块,1个D类模块

若N6包含1个A类模块,不妨设1个A模块的色集合{1311,1211,1411,1312}。{3,3,3,1}与{3,3,3,4}与两个第二类4-子集组合为B1模块,{4,4,4,1}与{4,4,4,3}与两个第二类4-子集组合为B2模块,{2,2,2,3}与{3,3,3,2}与两个第二类4-子集组合为C1模块,{2,2,2,4}与{4,4,4,2}与两个第二类4-子集组合为C2模块,{2,2,2,1}与三个第二类4-子集组合为D模块。

若C1模块的色集合为{2322,2123,2423,3233},则C2模块的色集合只能为{2422,2144,2344,4244},则B2模块没有{1,1,4,4}或{2,3,4,4},无法组合。

若C1模块的色集合为{2322,2133,2433,3233},则C2模块的色集合只能为{2422,2124,2324,4244}。

若B1模块的色集合为{3133,3234,3433,4134},则B2模块的色集合只能为{4344,4241,4144,1341}。故{1,2,2,3},{1,1,2,4},{1,2,3,4}必能与{2,2,2,1}组合为D模块。若{1,1,2,4}必能与{2,2,2,1}组合为D模块,且c5的色集合是{1,3,2,4},故顶点b6的色集合需要出现颜色2一次,颜色4一次且满足V条件,{1,2,2,3}不满足。若{1,1,2,4}必能与{2,2,2,1}组合为D模块,且c5的色集合是{1,3,2,2},故顶点b6的色集合需要出现颜色2两次,{1,2,3,4}不满足。故{1,2,2,3},{1,1,2,4},{1,2,3,4}无法与{2,2,2,1}组合为D模块。

若B1模块的色集合为{3133,3234,3433,4133},若B2模块的色集合为{4344,4241,4144,1341},则同上。若B2模块的色集合为{4344,4241,4144,1344},余下的子集为{1,2,2,3},{1,1,2,4},{1,1,3,4}必能与{2,2,2,1}组合为D模块,但{1,1,3,4}无颜色2。

C1模块的色集合有且仅有这两种,故在情形1.7中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.8 包含1个A类模块,3个B类模块,2个D类模块

若N6包含1个A类模块,不妨设1个A模块的色集合{1311,1211,1411,h}。h为{1,1,2,3}或{1,1,2,4}或{1,1,3,4}。{2,2,2,1}与{2,2,2,3}与两个第二类4-子集组合为B1模块,{3,3,3,1}与{3,3,3,2}与两个第二类4-子集组合为B2模块,{4,4,4,1}与{4,4,4,2}与两个第二类4-子集组合为B3模块,{2,2,2,4},{3,3,3,4},{4,4,4,3}的其中两个与两个第二类4-子集组合为D1,D2模块。

若B1模块的色集合为{2122,2423,2322,3123},B2模块的色集合为{3133,3432,3233,2132},B3模块的色集合为{4144,4342,4244,2142}。剩余的4-子集中只有{1,1,2,4},{1,2,4,4},{1,2,3,4}含颜色2,但{1,1,2,4}与{2,2,2,4}无法组合为D模块(与V条件矛盾),故D模块的色集合不包含{2,2,2,4}。同样{1,1,3,4}与{3,3,3,4},{4,4,4,3}都无法组合为D模块(与V条件矛盾)。

若B1模块的色集合为{2122,2423,2322,3123},B2模块的色集合为{3233,3431,3133,1231},B3模块的色集合为{4144,4342,4244,2142}。因{1,1,2,4}与{2,2,2,4}无法组合为D模块(与V条件矛盾),则剩余的4-子集中只有{1,2,2,3},{1,2,4,4},{2,3,3,4},{1,2,3,4}含颜色2。若{1,2,4,4}为a5的色集合,则c5的色集合是{4,3,2,1},故顶点b6的色集合需要出现颜色1一次,颜色2一次且满足V条件,余下4-子集不满足。故D模块的色集合不包含{2,2,2,4}。同样{1,1,3,4}与{3,3,3,4},{4,4,4,3}都无法组合为D模块(与V条件矛盾)。{1,3,4,4},{2,3,3,4},{1,2,3,4}必与{4,4,4,3}组合为D模块,故{1,3,4,4}为a5的色集合,则c5的色集合是{3,2,4,3},故顶点b6的色集合{3,1,4,2}。因此{1,2,2,3},{1,1,2,4},{1,2,4,4}必与{3,3,3,4}组合为D模块,但{1,1,2,4},{1,2,4,4}无颜色3。

若B1模块的色集合为{2122,2423,2322,3123},B2模块的色集合为{3133,3432,3233,2132},B3模块的色集合为{4244,4341,4144,1241}。因{1,1,3,4}与{3,3,3,4},{4,4,4,3}都无法组合为D模块(与V条件矛盾)。剩余的4-子集中只有{1,3,3,4},{2,3,4,4},{1,2,3,4}含颜色3,可与{3,3,3,4}组合为D模块。故{1,3,3,4}为a5的色集合,则c5的色集合是{4,2,3,4},故顶点b6的色集合{4,1,3,2}。且{1,1,3,4}不含颜色2,因{1,2,2,4},{1,2,4,4}可与{4,4,4,3}组合为D模块,但第二类4-子集个数不足。

若B1模块的色集合为{2122,2423,2322,3123},B2模块的色集合为{3233,3431,3133,1231},B3模块的色集合为{4244,4341,4144,1241}。剩余的4-子集中只有{1,2,2,3},{2,3,3,4},{2,3,4,4},{1,2,3,4}含颜色3,可与{3,3,3,4}组合为D模块。若{1,2,2,3}为a5的色集合,则c5的色集合需要出现颜色2一次,颜色3一次且满足V条件,余下4-子集不满足。若{2,3,3,4}为a5的色集合,则c5的色集合{3,2,4,3},则d5的色集合需要出现颜色2一次,颜色3一次且满足V条件,余下4-子集不满足。故D模块的色集合不包含{3,3,3,4}。剩余的4-子集中只有{1,2,2,4},{1,2,4,4},{2,3,3,4},{2,3,4,4},{1,2,3,4}含颜色4,可与{4,4,4,3}组合为D模块。若{1,2,2,4}为a5的色集合,则c5的色集合需要出现颜色2一次,颜色4一次且满足V条件,余下4-子集不满足。若{2,3,3,4}为a5的色集合,且c5的色集合{3,1,4,2},则d5的色集合需要出现颜色2一次,颜色4一次且满足V条件,余下4-子集不满足;若{2,3,3,4}为a5的色集合,且c5的色集合{3,2,4,3},则d5的色集合需要出现颜色3一次,颜色4一次且满足V条件,余下4-子集不满足。因此{1,2,4,4},{2,3,4,4},{1,2,3,4}必能与{4,4,4,3}组合为D模块。则D1模块的色集合为{2144,4234,4344,3142}。剩余的4-子集{1,2,2,3},{1,2,2,4},{2,3,3,4}必能与{2,2,2,4}组合为D模块。但{2,3,3,4}无法与{2,2,2,4}组合为D模块(与V条件矛盾)。

当B1模块的色集合为其他4-子集组合时同理。故在情形1。8中N6不存在顶点被多重集点可区别染色的4-E-全染色。

在只包含一个A类模块,分配其他三类模块的前提下,其余情形皆为第二类4-子集个数不足以满足,故省去。

情形1.9 包含6个C类模块

若N6包含6个C类模块,只能{1,1,1,2}与{2,2,2,1}与两个第二类4-子集组合为C1模块,{1,1,1,3}与{3,3,3,1}与两个第二类4-子集组合为C2模块,{1,1,1,4}与{4,4,4,1}与两个第二类4-子集组合为C3模块,{2,2,2,3}与{3,3,3,2}与两个第二类4-子集组合为C4模块,{2,2,2,4}与{4,4,4,2}与两个第二类4-子集组合为C5模块,{3,3,3,4}与{4,4,4,3}与两个第二类4-子集组合为C6模块。

若C1模块色集合{1211,1312,1412,2122},C2模块色集合只能是{1311,1233,1433,3133},C3模块色集合只能是{1411,1244,1344,4144},C4模块色集合只能是{2322,2123,2423,3233},但C5模块色集合需4-子集{2,2,3,4}或{1,2,4,4},上述两个子集都已使用,故无法组合为C5模块。

若C1模块色集合{1211,1322,1422,2122}同理。故在情形1.9中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.10 包含5个C类模块,1个D类模块

若N6包含5个C类模块,只能{1,1,1,2}与{2,2,2,1}与两个第二类4-子集组合为C1模块,{1,1,1,3}与{3,3,3,1}与两个第二类4-子集组合为C2模块,{1,1,1,4}与{4,4,4,1}与两个第二类4-子集组合为C3模块,{2,2,2,3}与{3,3,3,2}与两个第二类4-子集组合为C4模块,{2,2,2,4}与{4,4,4,2}与两个第二类4-子集组合为C5模块,{3,3,3,4},{4,4,4,3}其中一个与两个第二类4-子集组合为D模块。

同情形1.9,故在情形1.10中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.11 包含2个B类模块,4个C类模块

若N6包含4个C类模块,只能{1,1,1,2}与{2,2,2,1}与两个第二类4-子集组合为C1模块,{1,1,1,3}与{3,3,3,1}与两个第二类4-子集组合为C2模块,{1,1,1,4}与{4,4,4,1}与两个第二类4-子集组合为C3模块,{2,2,2,3}与{3,3,3,2}与两个第二类4-子集组合为C4模块,{4,4,4,2},{4,4,4,3}与两个第二类4-子集组合为B1模块,但{3,3,3,4},{2,2,2,4}无法与两个第二类4-子集组合为B2模块。(不满足B模块的组合条件)

故在情形1.11中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.12 包含1个B类模块,4个C类模块,1个D类模块

若N6包含4个C类模块,只能{1,1,1,2}与{2,2,2,1}与两个第二类4-子集组合为C1模块,{1,1,1,3}与{3,3,3,1}与两个第二类4-子集组合为C2模块,{1,1,1,4}与{4,4,4,1}与两个第二类4-子集组合为C3模块,{2,2,2,3}与{3,3,3,2}与两个第二类4-子集组合为C4模块,{4,4,4,2},{4,4,4,3}与两个第二类4-子集组合为B模块,{3,3,3,4}与{2,2,2,4}分别与两个第二类4-子集组合为D1,D2模块。(不满足B模块的组合条件)

若C1模块色集合{1211,1312,1412,2122},C2模块色集合只能是{1311,1233,1433,3133},C3模块色集合只能是{1411,1244,1344,4144},C4模块色集合只能是{2322,2123,2423,3233},但B模块色集合需4-子集{1,2,4,4}或{1,3,4,4},上述两个子集都已使用,故无法组合为B模块。

若C1模块色集合{1211,1322,1422,2122},若C2模块色集合是{1311,1213,1413,3133},C3模块色集合只能是{1411,1244,1344,4144},C4模块色集合只能是{2322,2133,2433,3233},但B模块色集合需4-子集{1,2,4,4}或{1,3,4,4},上述两个子集都已使用,故无法组合为B模块。若C2模块色集合是{1311,1233,1433,3133}且C3模块色集合是{1411,1214,1314,4144},但C4模块色集合需4-子集{1,2,2,3}或{1,2,3,3},上述两个子集都已使用,故无法组合为C4模块。若C2模块色集合是{1311,1233,1433,3133}且C3模块色集合是{1411,1244,1344,4144},但C4模块色集合需4-子集{1,2,2,3}或{1,2,3,3},上述两个子集都已使用,故无法组合为C4模块。

故在情形1.12中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.13 包含2个B类模块,3个C类模块,1个D类模块

若N6包含3个C类模块,不妨设{1,1,1,2}与{2,2,2,1}与两个第二类4-子集组合为C1模块,{1,1,1,3}与{3,3,3,1}与两个第二类4-子集组合为C2模块,{1,1,1,4}与{4,4,4,1}与两个第二类4-子集组合为C3模块,{2,2,2,3},{2,2,2,4};{3,3,3,2},{3,3,3,4};{4,4,4,2},{4,4,4,3}其中取两组与两个第二类4-子集组合为B1,B2模块,再从余下的一组中取一个与两个第二类4-子集组合为D模块。

若C1模块色集合{1211,1322,1422,2122},若C2模块色集合是{1311,1213,1413,3133},C3模块色集合只能是{1411,1244,1344,4144},若取{2,2,2,3},{2,2,2,4}与两个第二类4-子集组合为B1模块,但B1模块色集合需4-子集{1,2,2,3}或{1,2,2,4},上述两个子集都已使用,故无法组合为B1模块。若取{4,4,4,2},{4,4,4,3};与两个第二类4-子集组合为B1模块,但B1模块色集合需4-子集{1,2,4,4}或{1,3,4,4},上述两个子集都已使用,故无法组合为B1模块,则无法组合有两个B模块。

若C1模块色集合{1211,1322,1422,2122},若C2模块色集合是{1311,1213,1413,3133},C3模块色集合只能是{1411,1244,1344,4144},同理,无法组合有两个B模块。若C2模块色集合是{1311,1233,1433,3133}且C3模块色集合是{1411,1214,1314,4144},若取{2,2,2,3},{2,2,2,4}与两个第二类4-子集组合为B1模块,但B1模块色集合需4-子集{1,2,2,3}或{1,2,2,4},上述两个子集都已使用,故无法组合为B1模块。若取{3,3,3,2},{3,3,3,4};与两个第二类4-子集组合为B1模块,但B1模块色集合需4-子集{1,3,3,4}或{1,2,3,3},上述两个子集都已使用,故无法组合为B1模块,则无法组合有两个B模块。若C2模块色集合是{1311,1233,1433,3133}且C3模块色集合是{1411,1244,1344,4144},同理,无法组合有两个B模块。

故在情形1.13中N6不存在顶点被多重集点可区别染色的4-E-全染色。

情形1.14 包含4个B类模块,1个C类模块,1个D类模块

若N6包含1个C类模块,不妨设{1,1,1,2}与{2,2,2,1}与两个第二类4-子集组合为C模块,{1,1,1,3}与{1,1,1,4}与两个第二类4-子集组合为B1模块,{2,2,2,3}与{2,2,2,4}与两个第二类4-子集组合为B2模块,{3,3,3,1}与{3,3,3,2}与两个第二类4-子集组合为B3模块,{4,4,4,1}与{4,4,4,2}与两个第二类4-子集组合为B4模块,{3,3,3,4},{4,4,4,3}其中取一个与三个第二类4-子集组合为D模块。

若C模块色集合{1211,1312,1412,2122},B1模块色集合需4-子集{1,1,2,3}或{1,1,2,4},上述两个子集都已使用,故无法组合为B1模块。

若C模块色集合{1211,1322,1422,2122},B2模块色集合需4-子集{1,2,2,3}或{1,2,2,4},上述两个子集都已使用,故无法组合为B2模块。

故在情形1.14中N6不存在顶点被多重集点可区别染色的4-E-全染色。

在不包含A类模块,只分配其他三类模块的前提下,其余情形皆因第二类4-子集个数不足以满足情形条件,故省去。

综上所述,当 2 k 5 时, χ ˜ v t e ( N k ) 4 ,当k = 6时, χ ˜ v t e ( N k ) > 4

最后给出当 2 k 5 时,Nk的点被多重集可区别的4-E-全染色。

先给N2进行点被多重集可区别的4-E-全染色f2。f2 = (1311,1211,1411,1312;2422,2322,2122,2421)。

在N2的点被多重集可区别的4-E-全染色的基础上,给N3进行点被多重集可区别的4-E-全染色f3。f3 = (1311,1211,1411,1312;2422,2322,2122,2423;3213,1341,3144,1241)。

在N3的点被多重集可区别的4-E-全染色的基础上,给N4进行点被多重集可区别的4-E-全染色f4。f4 = (1311,1211,1411,1312;2422,2322,2122,2423;3213,1341,3144,1243;3433,3233,3133,3431)。

在N4的点被多重集可区别的4-E-全染色的基础上,给N5进行点被多重集可区别的4-E-全染色f5。f5 = (1311,1211,1411,1312;2422,2322,2122,2423;3213,1341,3144,1243;3133,3233,3433,3134;4244,4144,4344,4241)。

余{1,2,2,3},{1,1,2,4},{1,2,2,4},{2,3,4,4},{2,3,3,4}。

通过上述方式就可得出当 2 k 5 时,Nk的点被多重集可区别的4-E-全染色。

情形2 当 6 k 12 时, χ ˜ v t e ( N k ) = 5

6 k 13 η ˜ ( N k ) = 5 ,则由命题1, χ ˜ v t e ( N k ) 5 。但当k = 13时, η ˜ ( N k ) > 4 。证明与当k = 6时类似,故省去。

6 k 12 χ ˜ v t e ( N k ) 5 。故l = 5时,在N5的点被多重集可区别的4-E-全染色的基础上,进行如下过程:

[5,4,2,3,3,4;2,1]-S1型剖分运算,[5,3,4,2;1]-O3型剖分运算,[3,2,4,3;5]-T1型剖分运算,[4,3,2,4;5]-T1型剖分运算,[2,4,3,2;5]-T1型剖分运算,[1,2,3,4;5,5]-T2型剖分运算,余{1,1,4,5},{1,4,4,5}。

情形3 当 13 k 23 时, χ ˜ v t e ( N k ) = 6

14 k 26 η ˜ ( N k ) = 6 ,则由命题1, χ ˜ v t e ( N k ) 6 。但当k = 24、25、26时, η ˜ ( N k ) > 6 。证明与当k = 6时类似,故省去。

13 k 23 χ ˜ v t e ( N k ) 6 l = 6时,在N12的点被多重集可区别的5-E-全染色的基础上,进行如下过程:

[6,4,2,3,4,5;3,1]-S1型剖分运算,[6,5,3,4,4,5;3,2]-S1型剖分运算,[6,2,3,5;1]-O1型剖分运算,[6,4,2,5;1]-O1型剖分运算,[6,4,5,3;2]-O3型剖分运算,[4,3,5,4;6]-T1型剖分运算,[3,5,4,3;6]-T1型剖分运算,[2,6,1,2;5]-T1型剖分运算,[1,2,3,4;6,6]-T2型剖分运算,余{1,1,5,6},{1,5,5,6}。

情形4 当 24 k 42 时, χ ˜ v t e ( N k ) = 7

27 k 45 η ˜ ( N k ) = 7 ,则由命题1, χ ˜ v t e ( N k ) 7 。但当k = 43、44、45时, η ˜ ( N k ) > 7 。证明与当k = 6时类似,故省去。

24 k 42 χ ˜ v t e ( N k ) 7 。故l = 7时,在N23的点被多重集可区别的6-E-全染色的基础上,进行如下过程:

i依次为1,2,3进行[7,i + 3,i + 1,i + 2,5,6;4,i]-S1型剖分运算。

j依次为1,2令i依次为 j + 1 , j + 2 , , 3 进行[7,i,i + 1,6;j]-O1型剖分运算,令i依次为1,2进行[7,5,3,6; i] -O1型剖分运算,[7,5,6,4;3]-O3型剖分运算。

再进行[5,4,6,5;7]-T1型剖分运算,[6,5,4,6;7]-T1型剖分运算,[4,6,5,4;7]-T1型剖分运算,[2,3,5,6;7,6]-T2型剖分运算,[1,2,3,4;7,7]-T2型剖分运算,[7,4,5;1,2,6]-O4型剖分运算, [7,6,2,3;6,1]-O5型剖分运算,余{1,1,5,7}。

情形5 当 43 k 68 时, χ ˜ v t e ( N k ) = 8

46 k 73 η ˜ ( N k ) = 8 ,则由命题1, χ ˜ v t e ( N k ) 8 。但当k = 69,70,…,73时, η ˜ ( N k ) > 8 。证明与当k = 6时类似,故省去。

43 k 68 χ ˜ v t e ( N k ) 8 。故l = 8时,在N41的点被多重集可区别的7-E-全染色的基础上,进行如下过程:

i依次为1,2进行[8,i + 3,i + 1,i + 2,6,7;5,i]-S1型剖分运算,

j依次为1,2,3令i依次为 j + 1 , j + 2 , , 4 进行[8,i,i + 1,7;j]-O1型剖分运算,令i依次为1,2,3进行[8,6,4,7;i]-O1型剖分运算,之后再进行[8,6,7,5;4]-O3型剖分运算,[8,4,6;1,2,6]-O4型剖分运算,[8,2,5,6;3,7]-O5型剖分运算。

再进行[6,5,7,6;8]-T1型剖分运算,[7,6,5,7;8]-T1型剖分运算,[5,7,6,5;8]-T1型剖分运算,[1,2,3,4;8,8]-T2型剖分运算,[7,4,5,6,3,2;8]-S2型剖分运算,

最后 f D 68 = ( 7833 , 3518 , 3618 , 8187 )

余{1,1,5,8},{1,1,7,8},{1,2,5,8},{1,7,7,8}。

情形6 当 69 k 110 时, χ ˜ v t e ( N k ) = 9

74 k 112 η ˜ ( N k ) = 9 ,则由命题1, χ ˜ v t e ( N k ) 9 。但当k = 111、112时, η ˜ ( N k ) > 9 。证明与当k = 6时类似,故省去。

69 k 110 χ ˜ v t e ( N k ) 9 。故l = 9时,在N68的点被多重集可区别的8-E-全染色的基础上,进行如下过程:

i依次为1,2,3,4,5进行[9,i+3,i+1,i+2,7,8;6,i]-S1型剖分运算,

j依次为1,2,3,4,令i依次为 j + 1 , j + 2 , , 5 进行[9,i,i+1,8;j]-O1型剖分运算,令i依次为1,2,3,4,进行[9,7,5,8;i]-O1型剖分运算,之后再进行[9,7,8,6;5]-O3型剖分运算,[9,4,5;2,1,6]-O4型剖分运算,[9,6,7;2,1,8]-O4型剖分运算,[9,5,7;3,2,7]-O4型剖分运算,[9,6,7;4,3,8]-O4型剖分运算,[9,1,5,6;1,8]-O5型剖分运算,[6,7,4,5;1,2,9,2]-O6型剖分运算,[5,7,2,3;1,6,9,3]-O6型剖分运算, [6,8,5,7;2,4,9,2]-O6型剖分运算。

再进行[7,6,8,7;9]-T1型剖分运算,[8,7,6,8;9]-T1型剖分运算,[6,8,7,6;9]-T1型剖分运算,[4,2,3,5;8,9]-S3型剖分运算,

[1,2,3,4;9,9]-T2型剖分运算,[5,6,7,8;9,9]-T2型剖分运算。

余{1,1,7,9},{1,8,8,9},{1,4,6,9},{1,4,7,9}。

{1,1,7,9}与情形4所余子集{1,1,5,7},情形5所余子集{1,1,5,8},{1,1,7,8}组合,可得 f D 109 = ( 1517 , 1718 , 7911 , 8511 ) ,{1,4,6,9},{1,4,7,9}与情形1所余子集{1,1,4,5},{1,4,4,5}组合,可得 f D 110 = ( 5411 , 1694 , 1794 , 4145 ) ,最终余{1,8,8,9}。

情形7 当 111 k 165 时, χ ˜ v t e ( N k ) = 10

111 k 165 η ˜ ( N k ) = 10 ,则由命题1, χ ˜ v t e ( N k ) > 10 。故l=10时,在N110的点被多重集可区别的9-E-全染色的基础上,进行如下过程:

i依次为1,2,3,4,5,6进行[10,i+3,i+1,i+2,8,9;7,i]-S1型剖分运算,

j依次为1,2,3,4,5令i依次为 j + 1 , j + 2 , , 6 进行[10,i,i+1,9;j]-O1型剖分运算,令i依次为1,2,3,4,5进行[10,8,6,9;i]-O1型剖分运算,之后再进行[10,8,9,7;6]-O3型剖分运算,[5,8,7,6;10,1]-O2型剖分运算,[10,7,8;2,1,9]-O4型剖分运算,[10,5,6;3,2,7]-O4型剖分运算,[10,6,8;4,3,8]-O4型剖分运算,[10,7,8;5,4,9]-O4型剖分运算,[5,6,7,8;3,1,10,1]-O6型剖分运算,[7,8,2,4;1,6,10,4]-O6型剖分运算,[6,8,4,5;2,7,10,4]-O6型剖分运算,[6,8,7,9;2,3,10,2]-O6型剖分运算,

再进行[8,7,9,8;10]-T1型剖分运算,[9,8,7,9;10]-T1型剖分运算,[7,9,8,7;10]-T1型剖分运算,[6,9,8,7;10]-T1型剖分运算,令i依次为1,4进行[i,i+1,i+2,i+3;10,10]-T2型剖分运算,[10,9,3,5;9,4]-O5型剖分运算,最后 f D 160 = ( 10299 , 931010 , 91109 , 102910 ) f D 161 = ( 91033 , 37510 , 38510 , 101109 )

余{3,4,7,10},{2,5,8,10},{1,2,4,10},{1,2,5,10},{1,5,7,10},{1,5,8,10},其中{2,5,8,10}与情形5所余子集{1,2,5,8},情形6所余子集{1,8,8,9},情形1所余子集{1,2,2,3}组合,可进行[9,3,5,10;1]-O3型剖分运算,{1,2,4,10},{1,2,5,10}与情形1所余子集{1,1,2,4},{1,2,2,4}组合,可进行[2,1,10,5;4]-O3型剖分运算,{1,5,7,10},{1,5,8,10}与情形1所余子集{1,1,5,6},{1,5,5,6}组合,可进行[5,1,7,8;10,6]-O5型剖分运算。余{3,4,7,10},{2,3,4,4},{2,3,3,4},{1,7,7,8}。

将情形7的 f D 32 = ( 1755 , 5617 , 5317 , 7571 ) 重新与{1,7,7,8}组合,成为 f D 32 = ( 1577 , 7817 , 7615 , 7155 ) ,并将 f D 31 = ( 1733 , 3417 , 3617 , 7371 ) 与余出的{1,3,5,7}重新组合为 f D 31 = ( 1733 , 3517 , 3617 , 7371 ) , 其中 f D 31 可直接通过剖分加入Nk,此时余出子集{1,3,4,7}。将 f D 6 = ( 1511 , 1251 , 1351 , 1415 , 5122 , 2315 , 2415 , 5251 ) 拆为 f D 6 = ( 1511 , 1251 , 1351 , 1415 ) f D 7 = ( 1522 , 2315 , 2145 , 5251 ) ,其中 f D 7 可直接通过剖分加入Nk,再将 f D 32 f D 6 颜色“5”的边连在一起,此时两个钻石的左右连接边颜色都为“1”,可剖分进Nk的颜色为“1”边,由此余出子集{1,3,4,7}。则{3,4,7,10},{1,3,4,7}与情形1所余子集{2,3,4,4},{2,3,3,4}组合,可进行[3,4,1,10;7,2]-O5型剖分运算。

因此, N k ( 2 k 165 ) 存在点被多重集可区别的l-E-全染色。

4. 结语

根据反证法得到了 N k ( 2 k 165 ) 不存在点被多重集可区别的(l-1)-E-全染色,因此 N k ( 2 k 165 ) 存在点被多重集可区别的l-E-全染色。并且利用具体构造染色的方法将 N k ( 2 k 165 ) 存在点被多重集可区别的l-E-全染色具体给出。之后,可继续利用反证法,用具体构造染色的方法对k ≥ 166进行讨论,并给出相应的染色数。

参考文献

[1] Burris, A.C. and Schelp, R.H. (1997) Vertex-Distinguishing Proper Edge-Coloring. Journal Graph Theory, 26, 73-82.
https://doi.org/10.1002/(SICI)1097-0118(199710)26:2%3C73::AID-JGT2%3E3.0.CO;2-C
[2] 杨芳, 王治文, 陈祥恩, 马春燕. 完全图和星的合成的点可区别正常边染色[J]. 华东师范大学学报(自然科学版), 2013(5): 136-143.
[3] Michael, A. (2018) Henning and Pawaton Kaemawichanurat. Semipaired Domination in Claw-Free Cubic Graphs. Graphs and Combinatorics, 34, 819-844.
https://doi.org/10.1007/s00373-018-1916-6
[4] Yannakakis, M. and Gavril, F. (1980) Edge Dominating Sets in Graphs. SIAM Journal on Applied Mathematics, 38, 364-372.
https://doi.org/10.1137/0138030
[5] Michael, A. (2012) Henning and Christian Löwenstein. Locating-Total Domination in Claw-Free Cubic Graphs. Discrete Mathematics, 312, 3107-3116.
https://doi.org/10.1016/j.disc.2012.06.024
[6] Zhang, Z.F., Qiu, P.X., Xu, B.G., et al. (2008) Vertex-Distinguishing Total Coloring of Graphs. Ars Combinatoria, 87, 33-45.
[7] Chen, X.E., Gao, Y.P. and Yao, B. (2013) Vertex-Distinguishing IE-Total Colorings of Complete Bipartite Graphs (mhttps://doi.org/10.7151/dmgt.1659
[8] 寇艳芳, 陈祥恩, 王治文. 和 的点可区别的IE-全染色及一般全染色[J]. 山东大学学报(理学版), 2018, 53(8): 53-60.
[9] 陈祥恩, 马静静. 的点可区别的IE-全染色(p ≥ 1008) [J]. 电子与信息学报, 2020, 42(12): 3068-3073.
[10] 闫瑞敏, 陈祥恩. 的点可区别的IE-全染色(p ≥ 2028) [J]. 华东师范大学学报(自然科学版), 2022(2): 16-23.