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

楊佳睿, 陳祥恩

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

0 引 言

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

K3,4,p的點(diǎn)可區(qū)別一般全染色已被證明,K3,4,p的一般的點(diǎn)可區(qū)別全色數(shù)已經(jīng)給出.定義V=X∪Y∪Z為完全三部圖Km,n,p的頂點(diǎn)集合, 其中,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 準(zhǔn)備工作

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

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

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

表1 K3,4,p的點(diǎn)染色方案

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

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

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

定理1

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

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

情形2當(dāng) 499≤p≤1 006 時(shí),gvt(K3,4,p)=10.

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

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

斷言4當(dāng)499≤p≤1 006,Z的色集合中至多含有6個(gè) 1-子集.

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

下面闡述K3,4,1 006的 10-GVDTC染色方案,先分配{1,2,3,4,…,10} 的子集給K3,4,p的每個(gè)頂點(diǎn), 令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中點(diǎn)的色集合,詳細(xì)的邊染色與點(diǎn)染色方案可參照表1與表2所述給出.

情形3當(dāng)243≤p≤498 時(shí),gvt(K3,4,p)=9.

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

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

斷言6 當(dāng)243≤p≤498,Z的色集合中至多含有5個(gè) 1-子集.

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

下面闡述K3,4,498的 9-GVDTC染色方案,先分配{1,2,3,…,9}的子集給K3,4,p的每個(gè)頂點(diǎn), 令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中點(diǎn)的色集合,詳細(xì)的邊染色與點(diǎn)染色方案可參照表1與表2所述給出.

情形4當(dāng) 115≤p≤242 時(shí),gvt(K3,4,p)=8.

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

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

斷言8當(dāng) 115≤p≤242,Z的色集合中至多含有4個(gè) 1-子集.

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

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

情形5當(dāng) 51≤p≤114 時(shí),gvt(K3,4,p)=7.

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

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

斷言10當(dāng) 51≤p≤114,Z的色集合至多含有3個(gè) 1-子集.

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

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

情形6當(dāng) 19≤p≤50 時(shí),gvt(K3,4,p)=6.

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

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

斷言12當(dāng) 19≤p≤50,Z的色集合至多含有2個(gè) 1-子集.

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

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

情形7當(dāng) 5≤p≤18 時(shí),gvt(K3,4,p)=5.

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

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

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

斷言15當(dāng) 5≤p≤18,Z的色集合中至多含有1個(gè) 1-子集.

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

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

情形8當(dāng)p=4 時(shí),gvt(K3,4,p)=4.

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

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