簡(jiǎn)單圖的無(wú)圈著色.pdf

1、圖的著色問(wèn)題是由地圖的著色提出的，它是最著名的NP-完全問(wèn)題之一。圖的著色理論不僅在離散數(shù)學(xué)和組合分析等數(shù)學(xué)理論中有著廣泛的應(yīng)用，近年來(lái)，隨著生產(chǎn)管理、交通運(yùn)輸、軍事、計(jì)算機(jī)和通訊網(wǎng)絡(luò)等方面許多離散型問(wèn)題的出現(xiàn)與研究，圖論的著色問(wèn)題具體應(yīng)用在解決安排會(huì)議或考試的日程以避免沖突和安排化學(xué)品的存儲(chǔ)上以避免相互反應(yīng)等問(wèn)題上并取得了較好的效果。
　　圖的無(wú)圈著色和線性著色是在頂點(diǎn)著色的基礎(chǔ)上提出的。本文研究了幾類簡(jiǎn)單圖的無(wú)圈著色以及與之密

2、切相關(guān)的線性著色問(wèn)題，主要分為三部分：
　　在第一部分中（見(jiàn)論文第一、二章）對(duì)圖論著色問(wèn)題的研究歷史、背景、基本概念等進(jìn)行一個(gè)綜述。主要包括：正常頂點(diǎn)著色、無(wú)圈著色、星著色、3-不足著色和線性著色等，為后文的論證打好基礎(chǔ)。
　　第二部分（論文第三、四章）探討圖的無(wú)圈著色和線性著色問(wèn)題。
　　無(wú)圈著色在研究星著色、2-距離著色等問(wèn)題中具有重要意義，這類著色問(wèn)題通常會(huì)以無(wú)圈色數(shù)作為下界來(lái)逼近其色數(shù)的確界，因此在著色研究中只

3、要無(wú)圈著色有進(jìn)展，其他一系列著色就會(huì)有相應(yīng)的改進(jìn)。第三章通過(guò)分析圖的結(jié)構(gòu)，運(yùn)用歸納等數(shù)學(xué)理論方法給出了最大度為5的非正則圖和高度圖的無(wú)圈色數(shù)界，并通過(guò)群論中置換思想給出含有割邊或割點(diǎn)的五正則圖無(wú)圈色數(shù)的更加精確的上界。第四章首先運(yùn)用J.Heuvel的一個(gè)引理縮小了最大度大于11的平面圖的線性可選擇著色色數(shù)的上界；然后通過(guò)分析最大度為4的圖的著色特點(diǎn)得到了這一類圖線性色數(shù)的較為精確的上界，并給出具體算法說(shuō)明這個(gè)界是可達(dá)的；隨后證明了d維網(wǎng)