K3,5,p的點(diǎn)可區(qū)別的一般全染色

楊佳睿, 陳祥恩

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

0 引 言

目前, 關(guān)于圖的點(diǎn)可區(qū)別一般邊染色研究已有很多結(jié)果[1-7]. 文獻(xiàn)[8]提出了圖的一般點(diǎn)可區(qū)別全染色的概念. 圖G的一般全染色是指若干種顏色對(duì)圖G的全部頂點(diǎn)及邊的一個(gè)分配. 設(shè)f是圖G的一般全染色,x為G的一個(gè)頂點(diǎn), 將在f下x的顏色及與x關(guān)聯(lián)的邊的顏色所構(gòu)成的集合記為Cf(x)或C(x), 稱為頂點(diǎn)x在f下的色集合. 設(shè)f是圖G的一般全染色. 若對(duì)圖G的任意兩個(gè)不同的頂點(diǎn)u,v, 有C(u)≠C(v), 則f稱為圖G的點(diǎn)可區(qū)別一般全染色(簡(jiǎn)記為GVDTC). 對(duì)圖G進(jìn)行點(diǎn)可區(qū)別一般全染色所需的最少顏色數(shù)稱為G的點(diǎn)可區(qū)別一般全色數(shù), 記為χgvt(G). 圖G的k-一般全染色是指使用了k種顏色的圖G的一般全染色. 圖G的點(diǎn)可區(qū)別一般全染色也稱為圖G的一般點(diǎn)可區(qū)別全染色(簡(jiǎn)記為GVDTC)[8]. 圖G的k-一般點(diǎn)可區(qū)別全染色是指圖G使用了k種顏色的一般點(diǎn)可區(qū)別全染色(簡(jiǎn)記為k-GVDTC). 點(diǎn)可區(qū)別一般全色數(shù)也稱為一般點(diǎn)可區(qū)別全色數(shù). 文獻(xiàn)[8]研究了路、 圈、 星、 雙星、 三星、 輪、 扇和完全圖的一般點(diǎn)可區(qū)別全染色； 文獻(xiàn)[9-11]研究了另外幾類完全三部圖的點(diǎn)可區(qū)別一般全染色.

本文研究K3,5,p的點(diǎn)可區(qū)別一般全染色, 并給出其一般點(diǎn)可區(qū)別全色數(shù). 本文討論的完全三部圖Km,n,p的頂點(diǎn)集合為V=X∪Y∪Z, 邊集合為{xiyj|i=1,2,…,m;j=1,2,…,n}∪{yjzt|j=1,2,…,n;t=1,2,…,p}∪{xizt|i=1,2,…,m;t=1,2,…,p}, 其中:X={x1,x2,…,xm};Y={y1,y2,…,yn};Z={z1,z2,…,zp}. 本文約定給出一個(gè)圖的l-GVDTC時(shí), 所使用的l種顏色為1,2,…,l.

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

證明： 先用反證法證明K3,5,p不存在(l-1)-GVDTC, 再具體構(gòu)造出K3,5,p的l-GVDTC. 假設(shè)K3,5,p存在(l-1)-GVDTC.

斷言1) 任意1-子集都不是X∪Y中任一點(diǎn)的色集合.

斷言2) 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè)僅有{1},{2}這兩個(gè)集合不是Z中任一點(diǎn)的色集合, 則{3},{4},…,{l-1}均是Z中點(diǎn)的色集合, 即C(xi)∩C(yj)?{3,4,…,l-1}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4,…,l-1},{1,3,4,…,l-1},{2,3,4,…,l-1},{1,2,3,…,l-1}, 而這4個(gè)集合不能區(qū)分X,Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,p的一個(gè)l-GVDTCf. 令f(xi)=1(i=1,2,3),f(yj)=2(j=1,2,3,4,5). 用maxD(zi)染點(diǎn)zi(i=1,2,…,p). 而zi的關(guān)聯(lián)邊均染以i+6(i=1,2,…,l-6).

當(dāng)|D(zi)|=2時(shí),f(uzi)=min{D(u)∩D(zi)},u∈X∪Y. 當(dāng)|D(zi)|=3時(shí),f(uzi)=min{D(u)∩D(zi)},u∈{x2,x3,y1,y2,y3,y4,y5},f(x1zi)=min{D(x1)∩D(zi){f(x2zi),f(x3zi),f(yjzi)}},j=1,2,3,4,5. 當(dāng)|D(zi)|=4時(shí),f(uzi)=min{D(u)∩D(zi)},u∈{x3,y1,y2,y3,y4,y5},f(x2zi)=min{D(x2)∩D(zi){f(x3zi),f(yjzi)}},j=1,2,3,4,5;f(x1zi)=min{D(x1)∩D(zi){f(x2zi),f(x3zi),f(yjzi)}},j=1,2,3,4,5. 當(dāng)|D(zi)|=5時(shí),f(uzi)=min{D(u)∩D(zi)},u∈{y1,y2,y3,y4,y5},f(x3zi)=min{D(x3)∩D(zi){f(yjzi)}},j=1,2,3,4,5;f(x2zi)=min{D(x2)∩D(zi){f(x3zi),f(yjzi)}},j=1,2,3,4,5;f(x1zi)=min{D(x1)∩D(zi){f(x2zi),f(x3zi),f(yjzi)}},j=1,2,3,4,5. 當(dāng)|D(zi)|=6時(shí),f(uzi)=min{D(u)∩D(zi)},u∈{y2,y3,y4,y5},f(y1zi)=min{D(y1)∩D(zi){f(yjzi)}},j=2,3,4,5;f(x3zi)=min{D(x3)∩D(zi){f(yjzi)}},j=1,2,3,4,5;f(x2zi)=min{D(x2)∩D(zi){f(x3zi),f(yjzi)}},j=1,2,3,4,5;f(x1zi)=min{D(x1)∩D(zi){f(x2zi),f(x3zi),f(yjzi)}},j=1,2,3,4,5. 當(dāng)|D(zi)|=7時(shí),f(uzi)=min{D(u)∩D(zi)},u∈{y3,y4,y5},f(y2zi)=min{D(y2)∩D(zi){f(yjzi)}},j=3,4,5;f(y1zi)=min{D(y1)∩D(zi){f(yjzi)}},j=2,3,4,5;f(x3zi)=min{D(x3)∩D(zi){f(yjzi)}},j=1,2,3,4,5;f(x2zi)=min{D(x2)∩D(zi){f(x3zi),f(yjzi)}},j=1,2,3,4,5;f(x1zi)=min{D(x1)∩D(zi){f(x2zi),f(x3zi),f(yjzi)}},j=1,2,3,4,5. 當(dāng)|D(zi)|=8時(shí),f(uzi)= min{D(u)∩D(zi)},u∈{y4,y5},f(y3zi)=min{D(y3)∩D(zi){f(yjzi)}},j=4,5;f(y2zi)=min{D(y2)∩D(zi){f(yjzi)}},j=3,4,5;f(y1zi)=min{D(y1)∩D(zi){f(yjzi)}},j=2,3,4,5;f(x3zi)=min{D(x3)∩D(zi){f(yjzi)}},j=1,2,3,4,5;f(x2zi)=min{D(x2)∩D(zi){f(x3zi),f(yjzi)}},j=1,2,3,4,5;f(x1zi)=min{D(x1)∩D(zi){f(x2zi),f(x3zi),f(yjzi)}},j=1,2,3,4,5. 當(dāng)|D(zi)|=9時(shí),f(y5zi)=min{D(u)∩D(zi)},f(y4zi)=min{D(y4)∩D(zi){f(y5zi)}},f(y3zi)=min{D(y3)∩D(zi){f(yjzi)}},j=4,5;f(y2zi)=min{D(y2)∩D(zi){f(yjzi)}},j=3,4,5;f(y1zi)=min{D(y1)∩D(zi){f(yjzi)}},j=2,3,4,5;f(x3zi)=min{D(x3)∩D(zi){f(yjzi)}},j=1,2,3,4,5;f(x2zi)=min{D(x2)∩D(zi){f(x3zi),f(yjzi)}},j=1,2,3,4,5;f(x1zi)=min{D(x1)∩D(zi){f(x2zi),f(x3zi),f(yjzi)}},j=1,2,3,4,5.

對(duì)?x∈X,y∈Y, 用min{D(x)∩D(y)}染邊xy, 最后得到K3,5,p的l-IE全染色f, 是點(diǎn)可區(qū)別的, 因?yàn)?v∈V(K3,5,p), 均有C(v)=D(v).

2 主要結(jié)果

證明： 分以下8種情形進(jìn)行討論.

情形2) 當(dāng)1 009≤p≤2 028時(shí),χgvt(K3,5,p)=11.

先用反證法證明K3,5,p不存在10-GVDTC, 再構(gòu)造出K3,5,p的11-GVDTC. 假設(shè)K3,5,p存在10-GVDTC.

斷言① 任意1-子集均不是X∪Y中任一點(diǎn)的色集合.

斷言② 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè)僅有{1},{2}這兩個(gè)集合不是Z中任一點(diǎn)的色集合, 則{3},{4},…,{9}均是Z中點(diǎn)的色集合, 即有C(xi)∩C(yj)?{3,4,…,10}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4,…,10},{1,3,4,…,10},{2,3,4,…,10},{1,2,3,…,10}, 4個(gè)集合不能區(qū)分X,Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,2 028的11-GVDTC, 令D(x1)={1,2,…,11},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},D(y5)=D(x1){7}. 將除{1},{2},{3},{4},{5},{6},{7}外的{1,2,…,11}的其余1-子集,2-子集,…,9-子集作為Z中點(diǎn)的色集合, 參照引理2證明過程所述的染色法可給出K3,5,2 028的11-GVDTC.

情形3) 當(dāng)497≤p≤1 008時(shí),χgvt(K3,5,p)=10.

證明： 先用反證法證明K3,5,p不存在9-GVDTC, 再構(gòu)造出K3,5,p的10-GVDTC. 假設(shè)K3,5,p存在9-GVDTC.

斷言① 任意1-子集不是X∪Y中任一點(diǎn)的色集合.

斷言② 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè)僅有{1},{2}這兩個(gè)集合不是Z中任一點(diǎn)的色集合, 則{3},{4},…,{9}均是Z中點(diǎn)的色集合, 即有C(xi)∩C(yj)?{3,4,…,9}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4,…,9},{1,3,4,…,9},{2,3,4,…,9},{1,2,3,…,9}, 4個(gè)集合不能區(qū)分X,Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,1 028的10-GVDTC, 令D(x1)={1,2,…,10},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1) =D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},D(y5)=D(x1){7}. 將除{1},{2},{3},{4},{5},{6},{7}外的{1,2,…,10}的其余1-子集,2-子集,…,9-子集作為Z中點(diǎn)的色集合, 參照引理2證明過程所述的染色法可給出K3,5,1 008的10-GVDTC.

情形4) 當(dāng)241≤p≤496時(shí),χgvt(K3,5,p)=9.

證明： 先用反證法證明K3,5,p不存在8-GVDTC, 再構(gòu)造出K3,5,p的9-GVDTC. 假設(shè)K3,5,p存在8-GVDTC.

斷言① 任意1-子集不是X∪Y中任一點(diǎn)的色集合.

斷言② 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè)僅有{1},{2}這兩個(gè)集合不是Z中任一點(diǎn)的色集合, 則{3},{4},…,{8}均是Z中點(diǎn)的色集合, 即有C(xi)∩C(yj)?{3,4,…,8}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4,…,8},{1,3,4,…,8},{2,3,4,…,8},{1,2,3,…,8}, 4個(gè)集合不能區(qū)分X,Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,496的9-GVDTC, 令D(x1)={1,2,…,9},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},D(y5)=D(x1){7}. 將除{1},{2},{3},{4},{5},{6},{7}外的{1,2,…,9}的其余1-子集,2-子集,…,8-子集作為Z中點(diǎn)的色集合, 參照引理2證明過程所述的染色法可給出K3,5,496的9-GVDTC.

情形5) 當(dāng)113≤p≤240時(shí),χgvt(K3,5,p)=8.

證明： 先用反證法證明K3,5,p不存在7-GVDTC, 再構(gòu)造出K3,5,p的8-GVDTC. 假設(shè)K3,5,p存在7-GVDTC.

斷言① 任意1-子集不是X∪Y中任一點(diǎn)的色集合.

斷言② 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè)僅有{1},{2}這兩個(gè)集合不是Z中任一點(diǎn)的色集合, 則{3},{4},…,{7}均是Z中點(diǎn)的色集合, 即有C(xi)∩C(yj)?{3,4,…,7}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4,…,7},{1,3,4,…,7},{2,3,4,…,7},{1,2,3,…,7}, 4個(gè)集合不能區(qū)分X,Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,240的8-GVDTC, 令D(x1)={1,2,…,8},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},D(y5)=D(x1){7}. 將除{1},{2},{3},{4},{5},{6},{7}外的{1,2,…,8}的其余1-子集,2-子集,…,7-子集作為Z中點(diǎn)的色集合, 參照引理2證明過程所述的染色法可給出K3,5,240的8-GVDTC.

情形6) 當(dāng)49≤p≤112時(shí),χgvt(K3,5,p)=7.

證明： 先用反證法證明K3,5,p不存在6-GVDTC, 再構(gòu)造出K3,5,p的7-GVDTC. 假設(shè)K3,5,p存在6-GVDTC.

斷言① 任意1-子集不是X∪Y中任一點(diǎn)的色集合.

斷言② 任意2-子集均不是X∪Y中任一點(diǎn)的色集合.

斷言③ 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè)僅有{1},{2}這兩個(gè)集合不是Z中任一點(diǎn)的色集合, 則{3},{4},{5},{6}均是Z中點(diǎn)的色集合, 即有C(xi)∩C(yj)?{3,4,5,6}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4,5,6},{1,3,4,5,6},{2,3,4,5,6},{1,2,3,4,5,6}, 4個(gè)集合不能區(qū)分X,Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,112的7-GVDTC, 令D(x1)={1,2,…,7},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){5},D(y4)=D(x1){6},D(y5)=D(x1){7}. 將除{1},{2},{3},{4},{5},{6},{7}外的{1,2,…,7}的其余2-子集,3-子集,…,7-子集作為Z中點(diǎn)的色集合, 參照引理2證明過程所述的染色法可給出K3,5,112的7-GVDTC.

情形7) 當(dāng)17≤p≤48時(shí),χgvt(K3,5,p)=6.

證明： 先用反證法證明K3,5,p不存在5-GVDTC, 再構(gòu)造出K3,5,p的6-GVDTC. 假設(shè)K3,5,p存在5-GVDTC.

斷言① 任意1-子集不是X∪Y中任一點(diǎn)的色集合.

斷言②X∪Y中至多存在1個(gè)2-子集.

斷言③ 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè)僅有{1},{2}這兩個(gè)集合不是Z中任一點(diǎn)的色集合, 則{3},{4},{5}均是Z中點(diǎn)的色集合, 即有C(xi)∩C(yj)?{3,4,5}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4,5},{1,3,4,5},{2,3,4,5}，{1,2,3,4,5}, 4個(gè)集合不能區(qū)分X∪Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,48的6-GVDTC, 令D(x1)={1,2,…,6},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){1,2},D(y4)=D(x1){1,3},D(y5)=D(x1){1,4}. 將除{1},{2},{3},{4},{1,2},{1,3},{1,4}外的{1,2,…,6}的其余1-子集,2-子集,…,6-子集作為Z中點(diǎn)的色集合, 參照引理2證明過程所述的染色法可給出K3,5,48的6-GVDTC.

情形8) 當(dāng)5≤p≤16時(shí),χgvt(K3,5,p)=5.

證明： 先用反證法證明K3,5,p不存在4-GVDTC, 再構(gòu)造出K3,5,p的5-GVDTC. 假設(shè)K3,5,p存在4-GVDTC.

斷言① 任意1-子集不是X中任一點(diǎn)的色集合.

斷言② 任意1-子集不是Y中任一點(diǎn)的色集合.

斷言③ 至少3個(gè)1-子集不是Z中任一點(diǎn)的色集合.

否則, 不妨設(shè){1},{2}不是Z中任一點(diǎn)的色集合, 則{3},{4}是Z中點(diǎn)的色集合, 即有C(xi)∩C(yj)?{3,4}, 從而X,Y中每個(gè)點(diǎn)可分配的色集合有{3,4},{1,3,4},{2,3,4},{1,2,3,4}, 4個(gè)集合不能區(qū)分X,Y中的8個(gè)頂點(diǎn), 矛盾.

下面給出K3,5,16的5-GVDTC, 令D(x1)={1,2,…,5},D(x2)=D(x1){1},D(x3)=D(x1){2},D(y1)=D(x1){3},D(y2)=D(x1){4},D(y3)=D(x1){1,2},D(y4)=D(x1){1,3},D(y5)=D(x1){1,4}. 將除{1},{2},{3},{4},{1,2},{1,3},{1,4}外的{1,2,…,5}的其余1-子集,2-子集,…,5-子集作為Z中點(diǎn)的色集合, 參照引理2證明過程所述的染色法可給出K3,5,16的5-GVDTC.