完全四部图Kn1,n2,n3,n4的点被多重集可区别的一般全染色(n1≤n2=n3 2023-09-27 01:34:54王勇军陈祥恩 吉林大学学报(理学版)订阅 2023年5期 收藏关键词：子集中点区别 王勇军, 陈祥恩(西北师范大学 数学与统计学院, 兰州 730070)关于点可区别一般边染色[1]的研究目前已有很多结果: 文献[2]引入了点可区别一般全染色, 并研究了路、 圈、 星(即K1,n)、 双星、 三星、 轮、 扇和完全图的一般点可区别全染色, 确定了它们的一般点可区别全色数; 文献[3]研究了部分完全三部图的点可区别(被非多重集)的IE-全染色; 文献[4]提出了点被多重集可区别的IE-全染色及一般全染色, 且对完全二部图的点被多重集可区别的IE-全染色及一般全染色进行了研究; 文献[5]研究了mK4的点可区别(被非多重集)的一般全染色; 文献[6]利用组合分析及构造具体染色的方法探讨了完全二部图K2,n和K3,n的一般点可区别全染色问题; 文献[7]引入了近完全图的概念, 并根据其结构特征, 给出了近完全图的邻点可区别正常边色数.本文研究完全四部图Kn1,n2,n3,n4(n1≤n2=n31 预备知识从n个互不相同元素中取出r个构成的重复组合也称为r-组合.r-组合也是上述n个互不相同元素构成的集合的含有r个元素的多重子集合, 所以r-组合也称为r-多重子集或简称r-子集.本文约定: 在不特殊说明的情况下,r-子集中的元素按不减顺序排列.2 完全四部图的点被多重集可区别的一般全染色证明: 1) 首先给出当n1=n2=n3将1,2这两种色的(n2+n3+n4+1)-子集按{1,1,1,…,1,1,1},{1,1,1,…,1,1,2},{1,1,1,…,1,2,2},…,{1,1,2,…,2,2,2},{1,2,2,…,2,2,2},{2,2,2,…,2,2,2}排序, 并标号为1,2,…,3n1+3.将标号为2,3,…,n1+1的n1个子集依次对应到X1的n1个顶点上, 使得不同顶点对应不同的集合.最后, 给X4中每个点染颜色2, 这样所有的点及边已染好.下面说明在上述染色方案下, 不同点的色集合不同.(i) 若两个顶点属于不同的部, 则这两个点的色集合不同.由于X1,X2,X3中的点对应的集合对应(n2+n3+n4+1)-子集的不同标号, 且X4中点的色集合所含元素个数小于其他部顶点色集合所含元素个数, 故若两个顶点属于不同的部, 则这两个点的色集合不同.下面同时考虑定理1中的1)和2).当n4≥n1+2时, 在上述染色方案的基础上,X4中有部分点及边未染色, 给这部分顶点对应k种色的(n1+n2+n3+1)-子集且异于已确定的(n1+1)个子集,k≥2.证明: 1) 首先给出当n1设Ai,j为n4×1阶矩阵, 其中i,j分别表示矩阵中元素1的个数及元素2的个数.Ai,j中元素按不减顺序排列.设M为n4×(n1+n2+n3+1)阶矩阵,(i) 若两个顶点属于不同的部, 则这两个点的色集合不同.由于X1中点的色集合所含元素个数多于其他部点的色集合所含元素个数,X4中点的色集合所含元素个数少于其他部顶点色集合所含元素个数, 且X2,X3中点的色集合所含元素1的数目各不相同, 故若两个顶点属于不同的部, 则这两个点的色集合不同.关于2)中证明(k-1)种色为不能满足要求的染色, 与定理1中2)的证明类似, 故略.2) 由1)知, 当n4≥3时, 2种色为无法满足要求的染色.下面构造图G的使用了3种色的点被多重集可区别的一般全染色.综上所述, 本文解决了部分完全四部图的点被多重集可区别的一般全染色问题, 给出了染色方案, 得到的结果极具规律性.

王勇军, 陈祥恩

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

关于点可区别一般边染色[1]的研究目前已有很多结果: 文献[2]引入了点可区别一般全染色, 并研究了路、 圈、 星(即K1,n)、 双星、 三星、 轮、 扇和完全图的一般点可区别全染色, 确定了它们的一般点可区别全色数; 文献[3]研究了部分完全三部图的点可区别(被非多重集)的IE-全染色; 文献[4]提出了点被多重集可区别的IE-全染色及一般全染色, 且对完全二部图的点被多重集可区别的IE-全染色及一般全染色进行了研究; 文献[5]研究了mK4的点可区别(被非多重集)的一般全染色; 文献[6]利用组合分析及构造具体染色的方法探讨了完全二部图K2,n和K3,n的一般点可区别全染色问题; 文献[7]引入了近完全图的概念, 并根据其结构特征, 给出了近完全图的邻点可区别正常边色数.本文研究完全四部图Kn1,n2,n3,n4(n1≤n2=n3

1 预备知识

从n个互不相同元素中取出r个构成的重复组合也称为r-组合.r-组合也是上述n个互不相同元素构成的集合的含有r个元素的多重子集合, 所以r-组合也称为r-多重子集或简称r-子集.本文约定: 在不特殊说明的情况下,r-子集中的元素按不减顺序排列.

2 完全四部图的点被多重集可区别的一般全染色

证明: 1) 首先给出当n1=n2=n3

将1,2这两种色的(n2+n3+n4+1)-子集按{1,1,1,…,1,1,1},{1,1,1,…,1,1,2},{1,1,1,…,1,2,2},…,{1,1,2,…,2,2,2},{1,2,2,…,2,2,2},{2,2,2,…,2,2,2}排序, 并标号为1,2,…,3n1+3.将标号为2,3,…,n1+1的n1个子集依次对应到X1的n1个顶点上, 使得不同顶点对应不同的集合.

最后, 给X4中每个点染颜色2, 这样所有的点及边已染好.下面说明在上述染色方案下, 不同点的色集合不同.

(i) 若两个顶点属于不同的部, 则这两个点的色集合不同.由于X1,X2,X3中的点对应的集合对应(n2+n3+n4+1)-子集的不同标号, 且X4中点的色集合所含元素个数小于其他部顶点色集合所含元素个数, 故若两个顶点属于不同的部, 则这两个点的色集合不同.

下面同时考虑定理1中的1)和2).当n4≥n1+2时, 在上述染色方案的基础上,X4中有部分点及边未染色, 给这部分顶点对应k种色的(n1+n2+n3+1)-子集且异于已确定的(n1+1)个子集,k≥2.

证明: 1) 首先给出当n1

设Ai,j为n4×1阶矩阵, 其中i,j分别表示矩阵中元素1的个数及元素2的个数.Ai,j中元素按不减顺序排列.设M为n4×(n1+n2+n3+1)阶矩阵,

(i) 若两个顶点属于不同的部, 则这两个点的色集合不同.由于X1中点的色集合所含元素个数多于其他部点的色集合所含元素个数,X4中点的色集合所含元素个数少于其他部顶点色集合所含元素个数, 且X2,X3中点的色集合所含元素1的数目各不相同, 故若两个顶点属于不同的部, 则这两个点的色集合不同.

关于2)中证明(k-1)种色为不能满足要求的染色, 与定理1中2)的证明类似, 故略.

2) 由1)知, 当n4≥3时, 2种色为无法满足要求的染色.下面构造图G的使用了3种色的点被多重集可区别的一般全染色.

综上所述, 本文解决了部分完全四部图的点被多重集可区别的一般全染色问题, 给出了染色方案, 得到的结果极具规律性.