完全四部圖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種色的點被多重集可區別的一般全染色.
綜上所述, 本文解決了部分完全四部圖的點被多重集可區別的一般全染色問題, 給出了染色方案, 得到的結果極具規律性.
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=n3 從n個互不相同元素中取出r個構成的重復組合也稱為r-組合.r-組合也是上述n個互不相同元素構成的集合的含有r個元素的多重子集合, 所以r-組合也稱為r-多重子集或簡稱r-子集.本文約定: 在不特殊說明的情況下,r-子集中的元素按不減順序排列. 證明: 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種色的點被多重集可區別的一般全染色. 綜上所述, 本文解決了部分完全四部圖的點被多重集可區別的一般全染色問題, 給出了染色方案, 得到的結果極具規律性.1 預備知識
2 完全四部圖的點被多重集可區別的一般全染色
