圖的距離二邊標(biāo)號問題.pdf

1、在圖的經(jīng)典的頂點(diǎn)著色(或邊著色)中，我們只要求任意兩個(gè)相鄰頂點(diǎn)(或相鄰邊)所著顏色不相同.如果還要求距離為二的頂點(diǎn)(或距離為二的邊)所著顏色也不相同，我們就得到圖的距離二著色(或強(qiáng)邊著色).圖的距離二著色實(shí)際上就是原圖的平方圖的頂點(diǎn)著色.平方圖的頂點(diǎn)著色很早就有研究，而直到上個(gè)世紀(jì)九十年代初才出現(xiàn)一些圖的強(qiáng)邊著色的研究結(jié)果.經(jīng)典的頂點(diǎn)著色和邊著色已經(jīng)有非常豐富的理論結(jié)果，其應(yīng)用的領(lǐng)域也很廣泛.最近二十年來，關(guān)于圖的距離二著色問題和強(qiáng)邊著

2、色問題的研究結(jié)果也不斷涌現(xiàn).作為經(jīng)典著色問題的推廣，距離二著色問題和強(qiáng)邊著色問題研究進(jìn)一步拓廣了著色理論的實(shí)際應(yīng)用范圍.比如，Gebremedhin、Manne和Potthen在文[29]中綜述了距離二著色問題和一種強(qiáng)邊著色問題在導(dǎo)數(shù)計(jì)算中的應(yīng)用。 設(shè)j和k是兩個(gè)非負(fù)整數(shù)，通常假定j≥k，圖的L(j，k)-標(biāo)號是距離二著色的一個(gè)直接推廣，它最早是在1992年由Griggs和Yeh[38]為了解決一種特殊的頻道分配問題而提出的.它

3、作為經(jīng)典著色的一個(gè)重要推廣，得到了廣泛深入的研究.在圖的L(j，k)-標(biāo)號中，我們用非負(fù)整數(shù)對圖的頂點(diǎn)進(jìn)行標(biāo)號使得相鄰頂點(diǎn)的標(biāo)號之間的差至少為j而距離為二的頂點(diǎn)的標(biāo)號之間的差至少為k.一個(gè)圖的所有L(j，k)-標(biāo)號中最大標(biāo)號的最小值稱為該圖的L(j，k)-標(biāo)號數(shù)，圖的圓-L(j，k)-標(biāo)號是L(j，k)-標(biāo)號的一個(gè)變形，它用一個(gè)周長為整數(shù)的圓上的整點(diǎn)對圖的頂點(diǎn)進(jìn)行標(biāo)號，要求相鄰頂點(diǎn)的標(biāo)號在圓上的距離至少為j而距離為二的頂點(diǎn)的標(biāo)號在圓上的

4、距離至少為k.使得圖有圓-L(j，k)-標(biāo)號的最小圓的周長稱為圖的圓-L(j，k)-標(biāo)號數(shù)。我們可以類似地定義圖的L(j，k)-邊標(biāo)號數(shù)和圓-L(j，k)-邊標(biāo)號數(shù)，本論文重點(diǎn)研究圖的強(qiáng)邊著色(即圖的L(1，1)-邊標(biāo)號)、圖的L(2，1)-邊標(biāo)號和圖的圓-L(2，1)-邊標(biāo)號。 論文首先研究圖的強(qiáng)邊著色，證明除了一個(gè)僅六個(gè)頂點(diǎn)的特殊圖外，對任意圖G，如果對圖G的任一條邊xy都有d(x)+d(y)≤5，那么它的強(qiáng)邊色數(shù)不超過6.

5、因?yàn)橥耆繄DK2，3滿足上述條件且其強(qiáng)邊色數(shù)為6，所以上界6是最好可能的。這個(gè)結(jié)果回答了Faudree等人[22]提出的第四個(gè)問題，事實(shí)上我們不要求G是二部圖，所以這個(gè)結(jié)論比問題要求的更強(qiáng).該結(jié)果推進(jìn)了強(qiáng)邊色數(shù)上界的研究，有重要的理論意義.我們還設(shè)計(jì)了一個(gè)算法，它可以在線性時(shí)間內(nèi)對滿足上述定理?xiàng)l件的圖給出它的一個(gè)6-強(qiáng)邊著色，該算法具有潛在的應(yīng)用價(jià)值。 Georges和Mauro在文[33]中完全確定了無窮△-正則樹的L(2

6、，1)-邊標(biāo)號數(shù)，接著對任意正整數(shù)△，我們確定了無窮△-正則樹的圓-L(2，1)-邊標(biāo)號數(shù).設(shè)n≥2是一正整數(shù)，Qn，表示n-維立方體.Georges和Mauro在文[33]中研究了當(dāng)n較小時(shí)Qn的L(2，1)-邊標(biāo)號數(shù)，我們充分利用Qn的結(jié)構(gòu)特征和圓標(biāo)號的循環(huán)性質(zhì)確定了Q2、Q3、Q4和Q5的圓-L(2，1)-邊標(biāo)號數(shù)以及Q5的L(2，1)-邊標(biāo)號數(shù).我們在利用圓-L(2，1)-邊標(biāo)號數(shù)確定L(2，1)-邊標(biāo)號數(shù)這方面作了有益的嘗試，

7、有望使用這一手段確定更多的圖的L(2，1)-標(biāo)號數(shù)。 網(wǎng)格圖的研究是一項(xiàng)很有意義的工作，本論文最后集中研究三種無窮網(wǎng)格圖的L(2，1)-邊標(biāo)號、圓-L(2，1)-邊標(biāo)號和強(qiáng)邊著色.分別用г6、г4和г3表示無窮六邊形、四邊形和三角形網(wǎng)格圖，我們證明了г6的強(qiáng)邊色數(shù)為6，L(2，1)-邊標(biāo)號數(shù)為7，圓-L(2，1)-邊標(biāo)號數(shù)為8.用Pm□Pn表示兩條路Pm和Pn的笛卡爾乘積圖.我們又得到了一些情況下Pm口Pn的L(2，1)-邊標(biāo)號