楊佳睿, 陳祥恩
(西北師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 甘肅 蘭州 730070)
圖的(鄰)點可區(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}.
證明首先利用反證法.假設(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ū)別一般全染色.
定理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的全染色方案