楊佳睿, 陳祥恩

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

0 引 言

圖的(鄰)點可區(qū)別正常邊染色、(鄰)點可區(qū)別全染色及其相關(guān)猜想是受到當前國際著名圖論專家(如Bollobás等)重視的研究課題.1985年,Harary等[1]建設(shè)性地提出點可區(qū)別一般邊染色概念.1988年，Chartrand等[2]研究圖的非正規(guī)強度，即圖的可允許一般邊染色所需要顏色的最少數(shù)目；1997年Burris等[3]及1996年Hork等[4-6]分別獨立地提出圖的點可區(qū)別正常邊染色.Zagaglia[7]首次提出了點可區(qū)別的一般全染色概念.此后, 圖的可區(qū)別染色成為運籌方向的熱門領(lǐng)域，越來越多的學(xué)者投身其中，產(chǎn)出了許許多多相關(guān)成果.陳祥恩等[8-12]開辟了點可區(qū)別染色新方向，研究出許多新成果.點可區(qū)別的一般全染色是指滿足(鄰)點可區(qū)別及一般這兩個概念的色集合對圖的每個頂點的分配，其中，點可區(qū)別是指不同的點所分配的色集合均不相同，鄰點可區(qū)別則是指相鄰的點不能分配到相同的色集合.一般全染色是與正常全染色相對應(yīng)的概念.正常全染色需滿足三個條件，即相鄰的點不能染相同的顏色(V-條件)，相鄰的邊不能染相同的顏色(E-條件)，以及關(guān)聯(lián)的點與邊不能染相同的顏色(I-條件).而一般全染色則不需要滿足上述三個條件,在缺乏限制條件的情況下，色集合的分配也變得更加靈活和難以把握.事實上，圖的點可區(qū)別的E-全染色(VDETC)、點可區(qū)別的IE-全染色(VDIETC)、點可區(qū)別的I-全染色(VDITC),以及鄰點可區(qū)別的各種未必正常全染色，也是正在研究的課題.本文中出現(xiàn)了兩個概念，gvt(G)定義為G的一般的點可區(qū)別全色數(shù)，k-GVDTC定義為圖G的能夠使用k種顏色的點可區(qū)別一般全染色.

K3,4,p的點可區(qū)別一般全染色已被證明,K3,4,p的一般的點可區(qū)別全色數(shù)已經(jīng)給出.定義V=X∪Y∪Z為完全三部圖Km,n,p的頂點集合, 其中,X={x1,x2,…,xm},Y={y1,y2,…,yn},Z={z1,z2,…,zp}，邊集合為 {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}.

1 準備工作

證明首先利用反證法.假設(shè)K3,4,p有(l-1)-GVDTC.

反證法, 不妨設(shè)Z中包含{3},{4},…,{l-1}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,l-1}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,l-1}, {1,3,4,…,l-1}, {2,3,4,…,l-1}和 {1,2,3,4,…,l-1}這 4 個集可以分配給X∪Y中的7 個頂點, 顯然矛盾.

表1與表2給出K3,4,p的一個l-GVDTCf.

表1 K3,4,p的點染色方案

表2 K3,4,p的邊染色方案

因?v∈V(K3,4,p), 均有C(v)=D(v).故得到K3,4,p的l色的點可區(qū)別一般全染色.

2 主要結(jié)果及其證明

定理1

證明按照從一般到特殊分情形討論:

證明在引理 1、引理 2中已給出證明.

情形2當 499≤p≤1 006 時,gvt(K3,4,p)=10.

證明假設(shè)K3,4,p有 9-GVDTC.

斷言3 當499≤p≤1 006,?v∈X∪Y,|C(v)|≥6.

斷言4當499≤p≤1 006,Z的色集合中至多含有6個 1-子集.

反證法, 不妨設(shè)Z中包含{3},{4},…,{9}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,9}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,9}, {1,3,4,…,9}, {2,3,4,…,9}和 {1,2,3,4,…,9}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

下面闡述K3,4,1 006的 10-GVDTC染色方案,先分配{1,2,3,4,…,10} 的子集給K3,4,p的每個頂點, 令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},將除{1},{2},{3},{4},{5},{6}外的 {1,2,…,10}的其余子集作為Z中點的色集合,詳細的邊染色與點染色方案可參照表1與表2所述給出.

情形3當243≤p≤498 時,gvt(K3,4,p)=9.

證明：假設(shè)K3,4,p有 8-GVDTC.

斷言5 當243≤p≤498,K3,4,p的?v∈X∪Y,|C(v)|≥5.

斷言6 當243≤p≤498,Z的色集合中至多含有5個 1-子集.

反證法, 不妨設(shè)Z中包含{3},{4},…,{8}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,8}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,8}, {1,3,4,…,8}, {2,3,4,…,8}和 {1,2,3,4,…,8}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

下面闡述K3,4,498的 9-GVDTC染色方案,先分配{1,2,3,…,9}的子集給K3,4,p的每個頂點, 令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},將除{1},{2},{3},{4},{5},{6}外的 {1,2,…,9}的其余子集作為Z中點的色集合,詳細的邊染色與點染色方案可參照表1與表2所述給出.

情形4當 115≤p≤242 時,gvt(K3,4,p)=8.

證明假設(shè)K3,4,p有 7-GVDTC.

斷言7當 115≤p≤242,?v∈X∪Y,|C(v)|≥4.

斷言8當 115≤p≤242,Z的色集合中至多含有4個 1-子集.

反證法, 不妨設(shè)Z中包含{3},{4},…,{7}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,…,7}, 由于點染色滿足可區(qū)別性, 則只有{3,4,…,7}, {1,3,4,…,7}, {2,3,4,…,7}和 {1,2,3,4,…,7}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

K3,4,242的 8-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

情形5當 51≤p≤114 時,gvt(K3,4,p)=7.

證明假設(shè)K3,4,p有 6-GVDTC.

斷言9當 51≤p≤114,?v∈X∪Y,|C(v)|≥3.

斷言10當 51≤p≤114,Z的色集合至多含有3個 1-子集.

反證法, 不妨設(shè)Z中包含{3,4,5,6}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,5,6}, 由于點染色滿足可區(qū)別性,則只有{3,4,5,6}, {1,3,4,5,6}, {2,3,4,5,6}和{1,2,3,4,5,6}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

K3,4,114的 7-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

情形6當 19≤p≤50 時,gvt(K3,4,p)=6.

證明假設(shè)K3,4,p有 5-GVDTC.

斷言11當 19≤p≤50,?v∈X∪Y,|C(v)|≥3.

斷言12當 19≤p≤50,Z的色集合至多含有2個 1-子集.

反證法, 不妨設(shè)Z中包含{3,4,5}, 1-子集中僅僅不含{1},{2}這兩個集合,那么C(xi)∩C(yj)?{3,4,5}, 由于點染色滿足可區(qū)別性, 則只有{3,4,5}, {1,3,4,5}, {2,3,4,5}和{1,2,3,4,5}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

K3,4,50的 6-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

情形7當 5≤p≤18 時,gvt(K3,4,p)=5.

證明假設(shè)K3,4,p有 4-GVDTC.

斷言13當 5≤p≤18,X的色集合中不含1-子集.

斷言14當 5≤p≤18,Y的色集合中不含1-子集.

斷言15當 5≤p≤18,Z的色集合中至多含有1個 1-子集.

反證法, 不妨設(shè)Z中含有{3},{4},僅不含 {1},{2} 這兩個色集合,即C(xi)∩C(yj)?{3,4}, 由于點染色滿足可區(qū)別性, 則只有{3,4}, {1,3,4}, {2,3,4}和{1,2,3,4}這 4 個集合可以分配給X∪Y中的7 個頂點, 顯然矛盾.

K3,4,18的 5-GVDTC的詳細邊染色與點染色方案可參照表1與表2所述給出.

情形8當p=4 時,gvt(K3,4,p)=4.

證明假如K3,4,4有 3-GVDTC.使用的 3 種顏色為 1,2,3.那么可分配的色集合有 7 個,無法區(qū)分X∪Y∪Z中的至少 11 個頂點, 矛盾.此時，K3,4,4沒有 3-GVDTC.在表3中給出了K3,4,4的4-GVDTC.

表3 K3,4,4的全染色方案