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

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

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

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