在19世紀(jì)的英國(guó),奧古斯都.德.摩根（Augustus De Morgan）的學(xué)生弗雷德里克.格思里的哥哥弗朗西斯.格思里（Francis guthrie）在對(duì)英國(guó)地圖進(jìn)行染色時(shí)發(fā)現(xiàn),如果共同邊界的區(qū)域染不同的顏色,只需4種顏色就可以染完整個(gè)地圖,由此誕生了著名的四色猜想,染色理論研究也由此開(kāi)始.圖染色理論作為一個(gè)重要的圖論研究方向,一直被學(xué)者和專家所研究.其中,特殊圖類在圖論研究中用來(lái)做反例,充當(dāng)達(dá)到條件的極圖,因此,研究特殊圖的著色具有重要的理論意義和實(shí)際應(yīng)用價(jià)值.本文主要研究了幾類特殊圖（廣義皮特森圖,廣義謝爾賓斯基圖,點(diǎn)分裂圖）的性質(zhì)并得到了具體染色數(shù).第一章首先介紹了圖論中染色理論和特殊圖的發(fā)展歷程,并簡(jiǎn)單敘述了Grundy著色和多彩著色的研究現(xiàn)狀.然后,對(duì)廣義皮特森圖,廣義謝爾賓斯基和點(diǎn)分裂圖的構(gòu)造與意義做了簡(jiǎn)要的總結(jié).第二章通過(guò)研究廣義皮特森圖的Grundy著色,得到了廣義皮特森圖的一些性質(zhì),由于當(dāng)n≠2l且l≠1時(shí),廣義皮特森圖P（n,l）是3正則圖,因此我們根據(jù)它的結(jié)構(gòu)給出了具體的染色方案,并得到Grundy染色數(shù).第三章研究了幾類特殊圖的多彩染色,首先通過(guò)研究度不超... 

【文章來(lái)源】：天津師范大學(xué)天津市

【文章頁(yè)數(shù)】：47 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖１：皮特森圖??－

１???３??ＩＸＩ??２?Ｉ?２??＼?／??２???１１２???３??ＩＸ＞－＇－＜ＸＩ??３?１?２???１??圖１：?Ｇｒｕｎｄｙ?３著色??當(dāng)Ｇ?ｆ?＝?￡?＋?ｓ?ｇ?２￡且＾；為偶數(shù)時(shí)染色函數(shù)如下：對(duì)于下標(biāo)ｎ－ｓ?＋?１?ｇ?ｉ幺ｎ的頂點(diǎn)不能染??顏色１，２，故ｐ（ｉ；ｎ＿ｓ＋ｉ）＝…＝（ｐ（ｒｎ）?＝?３是合適的染色，對(duì)于下標(biāo)ｎ?－?＜ｓ?＋?ｌＳｉｇｎ的頂點(diǎn)不能??染顏色２，故ｐ（？＿ｓ＋１）二…＝＝?１也是合適的染色．??下面給出頂點(diǎn)％的染色函數(shù)：下標(biāo)ｎ?－?￡?＋?的染色函數(shù)如下：??＾）?＝?（２ｉｆ?〇－＾（ｎ－＊）（ｍ〇ｄ２），?（２．２３）??ｌ３ｉｆ?１?三?ｉ?—?（ｎ＿?ｔ）（ｍｏｄ?２）．??下標(biāo)ｍ?＋１＊?－?．ｔ?＋１?ｇ?ｉ?２頂，載的染色畫(huà)數(shù)．??＿）?＝?ｆ２ｉｆ?ｆ?ｆ?＋?￡）（ｍ°ｄ２）’?（２．２４）??ｌｌｉｆ?１?三?ｉ?—?（ｎ?—尤?＋?彳）（ｍｏｄ?２）．??由于頂點(diǎn)％ｉ－ｌ與、－２，?＾ｎ－ｌ和相連，由上述的染色方式知道，Ｗ（Ｕｎ－２）?＝?２，?＝?１，?＃（ｉ；ｎ＿ｉ）＝??３故，故選ｐ（Ｕｎ－ｉ）?＝?４是合理的．??當(dāng)￡?ｇ?ｔ?ｇ?２￡并且ｔ為奇數(shù)時(shí)類似可證．??當(dāng)ｎ之處并且￡為偶數(shù)時(shí)，類似于上述染色過(guò)程，綜上所述，證明完畢．??２．３相關(guān)猜想??在文獻(xiàn)［１２］中３?Ｇａｓｔｉｎｅａｕ等人得到下面的兩個(gè)重要的結(jié)論：??⑴如果Ｇ是；一個(gè)沒(méi)有導(dǎo)．出Ｃ＊４的ｃｕｂｉｃ?ｇｒａｐｈ，那么ｒ［Ｇ］?＝４．??：（２）若ｒ?ｆ?４，每一＾沒(méi)有導(dǎo)出．Ｇｉ的？＇？．正：貝丨Ｊ圈．，它的Ｇｍｎｄｙ色數(shù)為ｒ?＋?１．??基于ｉ述的結(jié)論，

是這樣一棵樹(shù)，它ｒ只有３■點(diǎn)和１＿點(diǎn)，設(shè)辦）＝３，其中ｒ鄰接三個(gè)頂點(diǎn)％如圖３所示．為了??證明這個(gè)定理，我們只需要給出算法將Ｔ２嵌入到乎面中，??Ｚ??／＜ＣＴ＼７＼??４?ｕｌ?４Ｖ＼?Ｖ２＼?４?Ｗｉ?＾２?？??圖３：樹(shù)圖??現(xiàn)在，我們用下面的方法將�。驳倪吳度肫矫妫紫龋澄覀兛紤]Ｔ中的邊咖ｅ?ｒ，?ｗ將??平面可分為兩部分，上半部分平面和下半部分平面如，３可按順時(shí)針?lè)较蚶@根２嵌入上半平??面可按順時(shí)針?lè)较蚶@根Ｗ依次嵌入下半平面．結(jié)構(gòu)如圖４所示．??顯然，任意兩條邊％�。逦澹ǎ裕�，那么呀ｅ?洇此在上半平面我們得到一個(gè)新的Ｈ??魚(yú)形《腳，如國(guó)４所本？二角形０：饑ｔ和ｚ：龍！分別用ａｗ－ｆａｃｅ．、ｆａｃｅ表不？這樣我們就完成了２??的孩子節(jié)點(diǎn)的嵌入??身、、＇??圖４：嵌入．圖示??我們?cè)冢郑ǎ裕┲兄饌�(gè)實(shí)現(xiàn)Ｖ?ｅ?ＫＴ）的嵌入．這里ｒｆ（ｖ）?＝?１或ｒｆ（ｖ）?＝?３．??如果＋）二１，則我們完成嵌入過(guò)程？當(dāng)？，）＝?３時(shí)，將繼續(xù)以下過(guò)程：??不失一般性，，假設(shè)在瓦⑵中有購(gòu)＾：購(gòu)Ｅ五⑵，我們可以將事袢的邊嵌入到ｚ％?－?ｆａｅｅ＿＃：同樣??的，對(duì)于《結(jié)構(gòu)如圖５所示．??＾Ｚｌ＞，?ＺＵ?Ｅ?＿Ｅ（Ｔ）嵌入時(shí)，洲１，洲２（篇１，篇２）可以依次嵌入到＾?－纟ｅｒｔ／ａｃｅＱｕ?－?ｆａｃｅ）中按順??時(shí)針?lè)较蚶@根頂點(diǎn)＋）旋轉(zhuǎn)．??在新的平面中，同樣，任意兩條邊Ｇ?Ｅ（ｒ），?Ｍ?Ｇ?Ｅ（Ｔ２），因此我們得到兩個(gè)新的三??角形吵２《和＃１＾２：結(jié)構(gòu)如圖５所不．??考慮頂點(diǎn)邊冊(cè)和洲２，＾２２，＾產(chǎn)生兩個(gè)二角形，分別用＾１?－?ｆａｃｅ和瑪－?ｆａｃｅ表??示．??假設(shè)我們已經(jīng)嵌入了（ｎ－２）－層頂點(diǎn)％ｎ＿２）．

【參考文獻(xiàn)】：
期刊論文
[1]Sierpiński圖與Sierpińskigasket圖的條件著色[J]. 宋興坤,梁曉東.  新疆大學(xué)學(xué)報(bào)(自然科學(xué)版). 2015(03)
[2]關(guān)于圖的Grundy著色[J]. 徐保根.  華東交通大學(xué)學(xué)報(bào). 2010(01)

碩士論文
[1]圖的條件染色和非正常條件染色[D]. 劉婷.山東師范大學(xué) 2013



本文編號(hào)：3623905