全著色臨界圖及鄰點(diǎn)可區(qū)別全著色.pdf

1、具有重要理論意義和實(shí)用價值的染色問題，一直是圖論中的熱點(diǎn)話題之一.離散系統(tǒng)、組合分析中的許多問題都可轉(zhuǎn)化為圖著色問題，例如，不含給定圖G作為子圖的n個頂點(diǎn)的圖的邊的最大數(shù)目就依賴于G的色數(shù).因此TR.Jensen和B.Toft斷言:圖著色理論在離散數(shù)學(xué)中處于中心地位.在現(xiàn)實(shí)生活中許多領(lǐng)域都會涉及到將某種對象的集合按照一定的規(guī)劃進(jìn)行分類的問題，例如排課表問題、儲存問題、任務(wù)分配、時間表問題、排序問題、電路安排等，都與圖著色理論密切相關(guān).<

2、br>　　圖著色是指對圖中的頂點(diǎn)、邊（對平面圖而言還有面）等按照一定的規(guī)則進(jìn)行分類.對象不同或規(guī)則不同，便有各式各樣的著色，如點(diǎn)著色、邊著色、全著色、強(qiáng)著色、鄰強(qiáng)邊著色、鄰點(diǎn)可區(qū)別全著色、點(diǎn)可區(qū)別全著色、邊面著色、完美著色等多種著色方式.
　　為了恰當(dāng)?shù)乇硎敬笮统W(wǎng)絡(luò)、存儲問題、時間安排和任務(wù)分配等研究課題中各元素之間的關(guān)系，圖的著色理論作為一種可行的工具被自然的引入.由于其良好的應(yīng)用背景，圖的著色理論已成為現(xiàn)在圖論領(lǐng)域中迅速發(fā)展

3、的分支之一.
　　討論著色問題時，一類特殊的圖-臨界圖起著非常重要的作用.本文第一章研究全著色臨界圖，全著色臨界圖分為全著色點(diǎn)臨界圖和全著色邊臨界圖，而我們著重分析全著色邊臨界圖的結(jié)構(gòu)性質(zhì)，在文獻(xiàn)[2]給出的結(jié)果的基礎(chǔ)上，作進(jìn)一步推廣，得到了一般的結(jié)論.
　　第二章引入鄰點(diǎn)可區(qū)別全著色.鄰點(diǎn)可區(qū)別全著色是全著色理論的一個最新研究方向，張忠輔等人提出圖的鄰點(diǎn)可區(qū)別全著色這個概念，得到了若干結(jié)果，并提出了有關(guān)猜想:對于每個頂點(diǎn)個