關(guān)于圖著色的若干參數(shù)的研究.pdf

1、本學(xué)位論文主要考慮圖的著色問題。圖的著色理論是圖論研究的重要內(nèi)容之一，并且在離散數(shù)學(xué)，組合數(shù)學(xué)和現(xiàn)實生活中都有著重要的應(yīng)用。隨著科技的發(fā)展和現(xiàn)實生活的需要，各種各樣的著色問題已被國內(nèi)外的學(xué)者廣泛推廣和研究，諸如全著色、無圈著色、強邊著色、星著色、強著色、r-強邊著色等。由于確定一個圖的點色數(shù)或邊色數(shù)是NP—完全問題，因此，確定圖的這些特殊著色數(shù)同樣是NP—完全的。目前對這些問題的討論基本上是在對一些圖做了一定的條件限制，從而對其進行的研

2、究。
　　本論文共分五章，我們主要研究了一類圖的r-強邊著色，完全立方Halin圖的2-距離著色、完全立方Halin圖的星著色和Halin圖的星著色等。其中，在第一章我們首先對圖論的發(fā)展及其應(yīng)用做了簡要的介紹，并且還給出了本論文常用的一些符號表示。
　　在第二章，我們主要介紹了本論文所研究內(nèi)容的研究背景、研究歷史和研究綜述，最后還給出了本文所研究的內(nèi)容；在第三章，我們主要研究了一類圖的r-強邊著色，并得到某一類圖的1-強邊著