圖的{P-,r-}-自由著色.pdf

1、圖的著色問題一直是圖論中的重要問題，并且在離散數(shù)學(xué)和組合分析中有著廣泛的應(yīng)用。很多領(lǐng)域所涉及的問題都與圖的著色理論相關(guān)，例如：排序問題、排課表問題、存儲(chǔ)問題等等，正是由于著色的理論意義和實(shí)用價(jià)值引起了世人的廣泛的興趣。本文主要研究一般圖和Sierpi(n)ski圖S(n，k)的{Pr}-自由著色并且研究了{(lán)P3}-自由著色在標(biāo)號(hào)問題中的應(yīng)用。具體研究?jī)?nèi)容如下：
　　 首先，綜述了一般圖的著色的概念和研究現(xiàn)狀，例如：頂點(diǎn)著色、無(wú)圈

2、著色、2-距離著色、星著色以及L(2，1)-標(biāo)號(hào)等，對(duì)于這些著色與標(biāo)號(hào)的研究方法可直接應(yīng)用于圖的{Pr}-自由著色，從而為后文的研究做一些鋪墊。
　　 其次，根據(jù)2-距離著色和星著色的特點(diǎn)，文章引入了{(lán)Pr}-自由著色：一個(gè)圖G的{Pr}-自由著色是正常的頂點(diǎn)著色并且使得長(zhǎng)為r-1的路上不能著雙色。首先通過運(yùn)用線圖構(gòu)造了一類特殊圖，證明了最大度為△的圖G的{P3}-自由色數(shù)的下界，見定理3.5，然后通過運(yùn)用概率的方法證明了最大度

3、為△的圖G的{P4}-自由色數(shù)，見定理3.13，從而推廣了文獻(xiàn)[1]中的最主要結(jié)果。
　　 最后，首先證明了特殊圖Sierpi(n)ski圖S(n，k)的{Pr}-自由色數(shù)并且給出了精確值，然后給出了{(lán)P3}-自由著色的一個(gè)在標(biāo)號(hào)問題上的應(yīng)用。通過S(n，k)的{P3}-自由著色，給出了S(n，k)的L(2，1)-標(biāo)號(hào)數(shù)并且證明了此標(biāo)號(hào)是均勻的，從而引入了均勻L(2，1)-標(biāo)號(hào)的概念(一個(gè)圖G的均勻L(2，1)-標(biāo)號(hào)是正常的L(