1. 引言
本文所探讨的图均为有限简单无向图。关于图的点可区别正常边染色与图的点可区别一般边染色目前已有较多结论 [1] - [7] 。2008年,Zhang [8] 等提出了点可区别的全染色及相关猜想,图的点可区别I-全染色及相关猜想由Chen等 [9] 在2014年给出。对于图在非多重集上的点可区别的未必正常的全染色已有许多研究 [10] [11] [12] 。图的任意两个不同顶点被非多重色集合可区别的一般边染色已有一定的研究进展 [13] 。本文考虑图在多重集上的点可区别的一类未必正常全染色。
设
为图G的一个一般全染色(未必正常)。若对
,
,
,有
,且
,
,有
,则称该染色f为图G的I-全染色。若在f下图G的任意两条相邻边染以不同颜色,则称f为VI-全染色。显然I-全染色是VI-全染色。图G使用了l种颜色进行I-全染色(VI-全染色),称为图G的l-I-全染色(l-VI-全染色)。
设f为图G的一般全染色。对
,将
或
(不引起混淆时)称为点x的多重色集合,是由点x的颜色与点x关联的边的颜色构成。
显然有
,若称f是点被多重色集合可区别的,是指对
,总有
。令
,
。
将
称为点被多重色集合可区别的l-I-全色数,将
称为点被多重色集合可区别的l-VI-全色数。用
表示图G的度为i的顶点的个数,
,这里
和
分别表示图G的最小度和最大度。规定
上式中加号前面的项表示点的色是其关联边的颜色之一,
表示从l种互异的颜色中取出i种互不相同的颜色的取法数,对每种这样的取法,点的色的取法共有i种,因此共有
种;加号后面的项表示点的色不是其关联边的颜色,此时点的多重色集合里的
种颜色互不相同,具有这种特点的
-子集,共有
个。
命题1.1
显然图G的点被多重色集合可区别的I-全染色一定是图的点被多重色集合可区别的VI-全染色,因此本文只需讨论图的最优点被多重色集合可区别的I-全染色,从而得到图的最优点被多重色集合可区别的VI-全染色。
2. 准备工作
为了方便在定理证明过程中构造最优的点被多重色集合可区别的I全染色和VI-全染色,我们先定义一类矩阵。对任意的
,构造
矩阵
,使矩阵
的元素是集合
的含l的多重3-子集或空集,对其进行分类:
,这3类子集在
中仅出现一次;其中第i行含有
个
:
设
,
,用
表示矩阵
的位于第
行和第
列相交处的元素按其在原矩阵中的相对位置构成
阶子矩阵。
定义1 矩阵
的12个元素(非空)恰为C12的某个点被多重色集合可区别的I全染色下C12全体顶点的多重色集合,则称由这12个元素构成的组为一个好组。
引理1 若
,则
的染色方案为确定每3行4列共12个3-子集为:
,
为一个好组,对C12的全体顶点进行分配。
当
,即前4列
中各顶点色集合为:组成一个好组,称这种染色方案为
-I-型染色方案。前4列进行染色后,第5列及之后的
列的3行4列子矩阵,
中各顶点色集合为:
组成一个好组,称这种染色方案为
-II-型染色方案。
经过I、II-型染色方案选出了所有的好组,剩下的非好组在每个
下进行相应的补法,补足为C12的好组。
当
时,经过I-型染色方案染色后,子矩阵
剩下的非好组3-子集共9个:
,再补足3个3-子集即补足为一个C12的好组;子矩阵
剩下的6个非好组3-子集,从中选取3个3-子集:
与
剩下的9个非好组3-子集凑成一个C12的好组,称此补法为
-补法。经过II-型染色方案染色后,第9列及之后的
列剩下的非好组3-子集分为:3行3列的非好组3-子集,4行4列的非好组3-子集,5行4列的非好组3-子集,这3类非好组3-子集循环出现。3行3列中的非好组3-子集共6个:
4行4列中的非好组3-子集共10个,其中
与5行4列中的11个非好组3-子集,凑成一个C12的好组,称此补法为
-补法,那么经过
-补法后5行4列的非好组3-子集还剩下3个:
,4行4列的非好组3-子集还剩下9个。那么在
-补法补足一个C12的好组后,将4行4列剩下的9个非好组3-子集与3行3列中的3个非好组3-子集:
凑成一个C12的好组,称此补法为
-补法。
综上,
时,在使用了所有可实行的I、II-型染色方案和
-补法,找到所有C12的好组后,剩下的3-子集:
(如果
存在的话,
)。
引理2 若
,经过引理1中的I、II-型染色方案选出了所有的好组,剩下的非好组在每个
下进行相应的补法,补足为C12的好组。
当
时,经过I-染色方案染色后,子矩阵
剩下的非好组3-子集共13个:
;选取子矩阵
剩下的非好组3-子集中的1个:
与
剩下的非好组3-子集中的11个3-子集凑成一个C12的好组
,称此补法为-补法。使用
-补法后,
剩下了2个非好组3-子集:
。第5列及之后的
列剩下的非好组3-子集分为:4行4列的非好组3-子集,3行3列的非好组3-子集,5行4列的非好组3-子集,这3类非好组3-子集循环出现。4行4列中的非好组3-子集共10个:
,3行3列中的非好组3-子集共6个:
,将3行3列中的非好组中的
和4行4列中的前9个非好组,凑成一个C12的好组,称此补法为
-补法,使用
-补法后,剩下了3行3列中的3个非好组3-子集:
。再将4行4列剩下的最后一个非好组
与5行4列中的11个非好组凑成一个C12的好组,称此补法为
-补法,使用
-补法后,剩下了5行4列中的3个非好组3-子集:
。
综上,
时,在使用了所有可实行的I、II-型染色方案和
-补法,找到所有C12的好组后,剩下的3-子集:
(如果
存在的话,
)。
引理3 若
,经过引理1中的I、II-型染色方案选出了所有的好组,剩下的非好组在每个
下进行相应的补法,补足为C12的好组。
当
时,经过I-染色方案染色后,子矩阵
剩下的非好组3-子集共5个:
。第5列及之后的
列剩下的非好组3-子集分为:5行4列的非好组3-子集,4行4列的非好组3-子集,3行3列的非好组3-子集,这3类非好组3-子集循环出现。3行3列中的非好组3-子集共6个,4行4列中的非好组3-子集共10个,将3行3列中的非好组中的
和4行4列中的前9个非好组,凑成一个C12的好组,称此补法为
-补法,使用
-补法后,剩下了3行3列中的3个非好组3-子集:
。将4行4列剩下的最后一个非好组
与5行4列中的11个非好组凑成一个C12的好组,称此补法为
-补法,使用
-补法后,剩下了5行4列中的3个非好组3-子集:
。
综上,
时,在使用了所有可实行的I、II-型染色方案和
-补法,找到所有C12的好组后,剩下的3-子集:
(如果
存在的话,
)。
3. 主要结果及其证明
定理3.1 若
,则
。
证明:显然
,因此我们可直接对
进行点被多重色集合可区别的l-I-全染色。
1)
,显然
,不是C12的一个好组,于是必有
,对第一个C12分配以:
进行点被多重色集合可区别的4-I-全染色,则不是在该染色下的C12的任意顶点的4个3-子集为:
。
2)
,显然
,在上述C12的点被多重色集合可区别的4-I-全染色的基础上,给第2个C12进行点被多重色集合可区别的5-I-全染色,分配如下3-子集:
进行点被多重色集合可区别的5-I-全染色,则不是在该染色下的C12的任意顶点的6个3-子集为:
。
3)
,
,在已构造的2C12的点被多重色集合可区别的5-I-全染色的基础上,从第3个C12进行点被多重色集合可区别的6-I-全染色,分配如下3-子集:
;第4个C12进行点被多重色集合可区别的6-I-全染色,分配如下3-子集:
进行点被多重色集合可区别的6-I-全染色,则不是在该染色下的4C12的任意顶点的6个3-子集为:
。
4)
,
,在已构造的4C12的点被多重色集合可区别的6-I-全染色的基础上,从第5个C12进行点被多重色集合可区别的7-I-全染色,分配如下3-子集:
;第4个C12进行点被多重色集合可区别的7-I-全染色,分配如下3-子集:
进行点被多重色集合可区别的7-I-全染色,则不是在该染色下的6C12的任意顶点的5个3-子集为:
。
5)
,
,在已构造的6C12的点被多重色集合可区别的7-I-全染色的基础上,从第7个C12进行点被多重色集合可区别的8-I-全染色,分配如下3-子集:
;第8个C12进行点被多重色集合可区别的8-I-全染色,分配如下3-子集:
;第9个C12进行点被多重色集合可区别的8-I-全染色,分配如下3-子集:
进行点被多重色集合可区别的8-I-全染色,则不是在该染色下的9C12的任意顶点的4个3-子集为:
。
6)
,
,在已构造的9C12的点被多重色集合可区别的8-I-全染色的基础上,从第10个C12进行点被多重色集合可区别的9-I-全染色,分配如下3-子集:
;第11个C12进行点被多重色集合可区别的9-I-全染色,分配如下3-子集:
;第12个C12进行点被多重色集合可区别的9-I-全染色,分配如下3-子集:
;第13个C12进行点被多重色集合可区别的9-I-全染色,分配如下3-子集:
。此时共染色13个C12,没有剩余的3-子集。
从正整数9开始递增,递归地进行如下过程,在已构造好的
的点被多重色集合可区别的
-I-全染色的基础上,对第
个C12到第
个C12的染色方案,叙述如下:
情形1 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色。
情形2 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
-补法后,将剩下的部分非好组3-子集补足为C12的好组,可以得到个C12的点被多重色集合可区别的l-I-全染色。
情形3 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,将剩下的部分非好组3-子集补足为C12的好组,可以得到
个C12的点被多重色集合可区别的l-I-全染色,此时得到
的点被多重色集合可区别的l-I-全染色。
情形4 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色。
情形5 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经
、
、
过–补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,此时得到
的点被多重色集合可区别的l-I-全染色。
情形6 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,此时得到
的点被多重色集合可区别的l-I-全染色。
情形7 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色。
情形8 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色;此时得到
的点被多重色集合可区别的l-I-全染色。
情形9 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,此时得到
的点被多重色集合可区别的l-I-全染色。
情形10 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色。
情形11 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色。
情形12 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形13 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形14 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形15 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形16 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形17 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形18 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形19 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形20 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形21 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形22 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形23当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形24 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
的点被多重色集合可区别的l-I-全染色。
情形25 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形26 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形27 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形28 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形29 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形30 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形31 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形32 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形33当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形34 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
进行点被多重色集合可区别的l-I-全染色。
情形35 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形36 当,
时,由引理3经过-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形37 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形38 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形39 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形40 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形41 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形42 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形43 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形44 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形45 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形46 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形47当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形48 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、进行点被多重色集合可区别的l-I-全染色。
情形49 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、进行点被多重色集合可区别的l-I-全染色。
情形50 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形51 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形52 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形53 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形54 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形55 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形56 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
进行点被多重色集合可区别的l-I-全染色。
情形57 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形58 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形59 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形60 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形61 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形62 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形63 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形64 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形65 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形66 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形67 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形68 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形69 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
、
进行点被多重色集合可区别的l-I-全染色。
情形70 当
,
时,由引理1经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形71 当
,
时,由引理2经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
进行点被多重色集合可区别的l-I-全染色。
情形72 当
,
时,由引理3经过
-I-型染色和
-II-型染色,选出所有C12的好组,选出所有C12的好组,再经过
、
、
-补法后,可以得到
个C12的点被多重色集合可区别的l-I-全染色,再将余下3-子集分配给
、
、
、
进行点被多重色集合可区别的l-I-全染色。
定理证毕。
定理3.2 若
,则
。
证明 由命题1.1与定理3.1即得此结论。