圖的[r,s,t]-著色.pdf

1、圖的[]rst?著色重慶大學碩士學位論文學生姓名：張新軍指導老師：龔劬教授專業(yè)：計算數學學科門類：理學重慶大學數理學院二OO八年四月重慶大學碩士學位論文中文摘要I摘要圖的著色是經典的圖論問題，圖的著色理論在離散數學中占有很重要的地位，并且在組合分析和實際生活中有著廣泛的應用。近年來多種著色問題被相繼提出并加以發(fā)展和應用。2007年，.AKemnitz和MMarangio提出了圖的[]rst?著色。由于[]rst?著色中有三個參數rst和

2、，研究起來有相當難度，所以目前對[]rst?著色研究的文獻非常少。本文分別就一般圖中的二部圖(星、路)、圈、扇圖、輪圖的[]rst?著色進行討論，并將一般圖的[]rst?著色推廣到超圖上。首先，綜述了一般圖的點著色、邊著色、全著色和()Lpq?標號的概念、研究現狀和全著色及()Lpq?標號的研究方法。圖的[]rst?著色是點著色、邊著色和全著色的推廣，且與()Lpq?標號的定義有一些類似之處，所以這些問題的研究方法可直接應用于圖的[]r

3、st?著色的研究。其次，由于特殊圖有著一些特殊的結構和性質，所以圖論的很多研究課題都可以從它們進行入手，以便找到更一般的規(guī)律。當然，對著色問題的研究也不例外。于是，在第三章中對二部圖（星、路）、圈、扇圖、輪圖等一些特殊圖的[]rst?色數進行研究，為以后進一步討論更一般的情況作一些鋪墊。對特殊圖的[]rst?色數的研究，首先證明了一般的二部圖當rst滿足一定條件時的[]rst?色數，接著對特殊的二部圖——星和路具體討論當它們滿足一定條件

4、時的[]rst?色數，然后討論當rst滿足一定條件時奇圈和偶圈的[]rst?色數，最后研究了扇圖和輪圖的[]rst?色數。因為當rst取不同的值時有可能產生不同的[]rst?色數，所以在討論圖的[]rst?著色時有必要先對變量rst取值進行一些限制。最后，超圖作為一般圖的推廣，同樣可以把著色理論推廣到超圖上，于是就產生了超圖的著色。關于超圖的著色的內容也非常豐富，在第四章中，首先綜述了一些超圖著色概念及研究現狀，然后利用一般圖[]rst

5、?著色定義的方法，相應地把它推廣到超圖上，于是就提出了超圖的[]rst?著色顯然它是超圖的強點著色、強邊著色和強全著色的推廣。關于超圖的[]rst?著色，首先得到它的一些性質，如定理4.2.3，定理4.2.4；然后證明了當min0rst?時超圖的[]rst?色數，如定理4.2.6－定理4.2.9；最后證明了當r和s滿足一定條件時的11()rH?和11()sH?，并給出了11()tH?的上下界，詳見定理4.2.10－定理4.2.12。關鍵