完全二部圖的點(diǎn)被多重集可區(qū)別的IE-全染色及一般全染色

陳祥恩, 王勇軍

(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 蘭州 730070)

圖的點(diǎn)可區(qū)別一般邊染色由文獻(xiàn)[1]提出; 文獻(xiàn)[2]引入了圖的點(diǎn)可區(qū)別一般全染色的概念, 并且研究了路、 圈、 星(即K1,n)、 雙星、 三星、 輪、 扇和完全圖的一般點(diǎn)可區(qū)別全染色, 確定了它們的一般點(diǎn)可區(qū)別全色數(shù)； 文獻(xiàn)[3-6]研究了圖的點(diǎn)可區(qū)別(被非多重集)IE-全染色, 并考慮了完全三部圖； 文獻(xiàn)[7-8]研究了圈的點(diǎn)可區(qū)別(被非多重集)Ⅰ-全染色及Ⅵ-全染色.本文考慮點(diǎn)被多重集可區(qū)別的IE-全染色及點(diǎn)被多重集可區(qū)別的一般全染色, 研究完全二部圖的點(diǎn)被多重集可區(qū)別的IE-全染色及點(diǎn)被多重集可區(qū)別的一般全染色, 并確定完全二部圖Km,n的點(diǎn)被多重集可區(qū)別的IE-全色數(shù)及點(diǎn)被多重集可區(qū)別的一般全色數(shù).

1 預(yù)備知識(shí)

圖G的一般全染色是指若干種顏色對(duì)于圖G的全體頂點(diǎn)及邊的一個(gè)分配.圖G使用了k種顏色的一般全染色稱為圖G的k-一般全染色.圖G的IE-全染色是指使得相鄰頂點(diǎn)染以不同顏色的一個(gè)一般全染色.圖G使用k種顏色的IE-全染色稱為圖G的k-IE-全染色.

從n個(gè)互不相同元素中取出r個(gè)元素構(gòu)成的重復(fù)組合稱為r-組合.r-組合是前述n個(gè)互不相同元素構(gòu)成的集合中含有r個(gè)元素的多重子集合, 所以r-組合也稱為r-多重子集或r-子集.通常情況下, 進(jìn)行染色時(shí)所用的k種顏色用1,2,…,k表示, 且數(shù)字代表的顏色之間有大小關(guān)系.本文約定r-子集中的元素按照不減順序排列.

2 完全二部圖的點(diǎn)被多重集可區(qū)別的IE-全染色

綜上可得K1,n的點(diǎn)被多重集可區(qū)別的k-IE-全染色.證畢.

當(dāng)m>2時(shí),m+2<2m, 兩種顏色的(m+2)個(gè)(m+1)-子集不能區(qū)別所有頂點(diǎn).所以Km,m不存在點(diǎn)被多重集可區(qū)別的2-IE-全染色.

下面說(shuō)明諸ui的色集合各不相同.由染色方案可知, 隨著i的增大,ui的色集合中顏色2的個(gè)數(shù)嚴(yán)格增多, 故諸ui的色集合也各不相同.從而得到了Km,m的點(diǎn)被多重集可區(qū)別的3-IE-全染色.

下面利用矩陣更清晰地展示染色方案, 給出一個(gè)m+1行、m+1列的矩陣:

該矩陣中第1行元素除0外恰好是u1,u2,…,um的顏色, 第1列元素除0外恰好是v1,v2,…,vm的顏色, 第j行、 第i列相交處的元素恰好是邊ui-1vj-1的顏色,i,j≥2.因此第j行元素恰好構(gòu)成vj-1的色集合, 矩陣的第i列恰好構(gòu)成ui-1的色集合,i,j≥2.

下面說(shuō)明諸ui的色集合各不相同.由染色方案可知, 隨著i的增大,ui的色集合中顏色2的個(gè)數(shù)嚴(yán)格增多, 故諸ui的色集合也各不相同.從而得到了Km,m+1的點(diǎn)被多重集可區(qū)別的2-IE-全染色.

下面利用矩陣更清晰地展示染色方案, 給出一個(gè)m+2行、m+1列的矩陣:

該矩陣第1行元素除0外恰好是u1,u2,…,um的顏色, 第1列元素除0外恰好是v1,v2,…,vm+1的顏色, 第j行、 第i列相交處的元素恰好是邊ui-1vj-1的顏色,i,j≥2.因此, 矩陣的第j行元素恰好構(gòu)成vj-1的色集合, 矩陣的第i列元素恰好構(gòu)成ui-1的色集合,i,j≥2.

證明: 先證明Km,n不存在使用了(k-1)種色的點(diǎn)被多重集可區(qū)別的IE-全染色.

下面構(gòu)造使用k種色的點(diǎn)被多重集可區(qū)別的IE-全染色f.將{1,2,…,k}的所有(m+1)-子集(多重集)排成一個(gè)序列, 并使前(m+1)個(gè)(m+1)-子集分別是{1,1,1,…,1,1,1},{1,1,1,…,1,1,2},{1,1,1,…,1,2,2},…,{1,2,2,…,2,2,2}.令該序列的前n個(gè)子集依次對(duì)應(yīng)頂點(diǎn)v1,v2,…,vn.給頂點(diǎn)vj染對(duì)應(yīng)于它的(m+1)-子集中的第1個(gè)元素(顏色), 邊uivj染對(duì)應(yīng)于vj的(m+1)-子集中的第(i+1)個(gè)元素(顏色), 頂點(diǎn)ui染顏色k,i=1,2,…,m,j=1,2,…,n.此時(shí), 所得染色是IE-全染色,vj的色集合恰好是對(duì)應(yīng)于vj的(m+1)-子集, 因此,v1,v2,…,vm的色集合各不相同,vj與ui的色集合也不相同, 因?yàn)関j與ui的色集合中元素個(gè)數(shù)不同,i,j=1,2,…,m.從而得到了Km,n的點(diǎn)被多重集可區(qū)別的k-IE-全染色.

該矩陣第1行元素除0外恰好是u1,u2,…,um的顏色, 第1列元素除0外恰好是v1,v2,…,vn的顏色, 第j行、 第i列相交處的元素恰好是邊ui-1vj-1的顏色,i,j≥2.因此矩陣的第j行元素恰好構(gòu)成vj-1的色集合, 矩陣的第i列元素恰好構(gòu)成ui-1的色集合,i,j≥2.

3 完全二部圖的點(diǎn)被多重集可區(qū)別一般全染色

設(shè)頂點(diǎn)vj對(duì)應(yīng)的3-子集為{a,b,c},a≤b≤c.令a染點(diǎn)vj,b染邊u1vj,c染邊u2vj.從而所有2度點(diǎn)以及相關(guān)聯(lián)的邊都已染好.最后, 用k染點(diǎn)u1,u2.顯然, 每個(gè)2度頂點(diǎn)vj的色集合均為事先對(duì)應(yīng)于它的3-子集.度不同的兩個(gè)頂點(diǎn)的色集合一定不相同.因此在所構(gòu)造出的染色下, 各頂點(diǎn)的色集合互不相同.于是得到了K2,n的點(diǎn)被多重集可區(qū)別的一般全染色.證畢.

下面給出染色方案.令m個(gè)(m+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}分別對(duì)應(yīng)頂點(diǎn)v1,v2,…,vm.給頂點(diǎn)vj染顏色1, 邊uivj染對(duì)應(yīng)于vj的(m+1)-子集中的第(i+1)個(gè)元素(顏色), 頂點(diǎn)ui染顏色3,i=1,2,…,m,j=1,2,…,m.此時(shí), 所得染色是一般全染色,vj的色集合恰好是對(duì)應(yīng)于vj的(m+1)-子集, 因此v1,v2,…,vm的色集合各不相同,vj與ui的色集合也不相同, 因?yàn)閡i的色集合中含3, 而vj的色集合中不含3,i,j=1,2,…,m.

下面說(shuō)明諸ui的色集合各不相同.由染色方案可知, 隨著i的增大,ui的色集合中顏色2的個(gè)數(shù)嚴(yán)格增多, 故諸ui的色集合也各不相同.從而得到了Km,m的使用了3種顏色的點(diǎn)被多重集可區(qū)別的一般全染色.

下面利用矩陣更清晰地展示染色方案, 給出一個(gè)m+1行、m+1列的矩陣:

該矩陣第1行元素除0外恰好是u1,u2,…,um的顏色, 第1列元素除0外恰好是v1,v2,…,vm的顏色, 第j行、 第i列相交處的元素恰好是邊ui-1vj-1的顏色,i,j≥2.因此, 矩陣的第j行元素恰好構(gòu)成vj-1的色集合, 矩陣的第i列元素恰好構(gòu)成ui-1的色集合,i,j≥2.

下面說(shuō)明諸ui的色集合各不相同.由染色方案可知, 隨著i的增大,ui的色集合中顏色2的個(gè)數(shù)嚴(yán)格增多, 故諸ui的色集合也各不相同.從而得到了Km,m+1的使用2種顏色的點(diǎn)被多重集可區(qū)別的一般全染色.

下面利用矩陣更清晰地展示染色方案, 給出一個(gè)m+2行、m+1列的矩陣:

該矩陣第1行元素除0外恰好是u1,u2,…,um的顏色, 第1列元素除0外恰好是v1,v2,…,vm+1的顏色, 第j行、 第i列相交處的元素恰好是邊ui-1vj-1的顏色.因此, 矩陣的第j行元素恰好構(gòu)成vj-1的色集合, 矩陣的第i列元素恰好構(gòu)成ui-1的色集合,i,j≥2.

下面說(shuō)明諸ui的色集合各不相同.由染色方案可知, 隨著i的增大,ui的色集合中顏色2的個(gè)數(shù)嚴(yán)格增多, 故諸ui的色集合也各不相同.從而得到了Km,m+2的使用2種顏色的點(diǎn)被多重集可區(qū)別的一般全染色.

下面利用矩陣更清晰地展示染色方案, 給出一個(gè)m+3行、m+1列的矩陣:

該矩陣第1行元素除0外恰好是u1,u2,…,um的顏色, 第1列元素除0外恰好是v1,v2,…,vm+2的顏色, 第j行、 第i列相交處的元素恰好是邊ui-1vj-1的顏色,i,j≥2.因此, 矩陣的第j行元素恰好構(gòu)成vj-1的色集合, 矩陣的第i列元素恰好構(gòu)成ui-1的色集合,i,j≥2.

下面構(gòu)造使用k種顏色的點(diǎn)被多重集可區(qū)別的一般全染色f.將{1,2,…,k}的所有(m+1)-子集(多重集)排成一個(gè)序列, 并使前(m+1)個(gè)(m+1)-子集分別是{1,1,1,…,1,1,1},{1,1,1,…,1,1,2},{1,1,1,…,1,2,2},…,{1,2,2,…,2,2,2}.令該序列的前n個(gè)子集依次對(duì)應(yīng)頂點(diǎn)v1,v2,…,vn, 給頂點(diǎn)vj染(m+1)-子集中的第一個(gè)元素(顏色), 邊uivj染對(duì)應(yīng)于vj的(m+1)-子集中的第(i+1)個(gè)元素(顏色), 頂點(diǎn)ui染顏色k,i=1,2,…,m,j=1,2,…,n.此時(shí), 所得染色是一般全染色,vj的色集合恰好是對(duì)應(yīng)于vj的(m+1)-子集, 因此,v1,v2,…,vm的色集合各不相同,vj與ui的色集合也不相同, 因?yàn)関j與ui的色集合中元素個(gè)數(shù)不同,i,j=1,2,…,m.從而得到了Km,n的使用了k種顏色的點(diǎn)被多重集可區(qū)別的一般全染色.證明諸ui色集合各不相同的方法與定理3相同, 故略.

該矩陣第1行元素除0外恰好是u1,u2,…,um的顏色, 第1列元素除0外恰好是v1,v2,…,vn的顏色, 第j行、 第i列相交處的元素恰好是邊ui-1vj-1的顏色,i,j≥2.因此, 矩陣的第j行元素恰好構(gòu)成vj-1的色集合, 矩陣的第i列元素恰好構(gòu)成ui-1的色集合,i,j≥2.