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

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

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

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

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

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