極大平面圖的構(gòu)造方法與幾類特殊圖的色數(shù)分析.pdf

1、圖論是離散數(shù)學(xué)的重要分支之一。著色問題是圖論中研究較早的領(lǐng)域，也是圖論的重要研究內(nèi)容，最近幾年來一直是圖論研究中的熱點問題，但至今著色問題仍是數(shù)學(xué)中未解決的難題之一。由于還未找到求圖色數(shù)的有效算法，甚至還未找到有較好性能比的有效近似算法，著色理論的應(yīng)用受到了很大的限制，這有待于我們?nèi)ミM一步的研究。 本文首先簡單介紹了目前國內(nèi)外關(guān)于圖的著色問題的研究現(xiàn)狀以及研究意義。其次，通過研究極大平面圖的構(gòu)成原理，給出了構(gòu)造極大平面圖的加點法

2、，并證明了這種方法的可靠性。接著，本文給出了簡單連通圖的色數(shù)不大于2的充要條件。接下來，本文證明了任意一個簡單平面圖都是某個極大平面圖的生成子圖，則任意一個簡單平面圖色數(shù)的上界是相應(yīng)的極大平面圖的色數(shù)。接著，本文證明了頂點度都為偶數(shù)的極大平面圖的色數(shù)為3。最后，本文在證明極大平面圖都可以5.著色的基礎(chǔ)上，用數(shù)學(xué)歸納法證明了部分加點法產(chǎn)生的極大平面圖是可以4.著色的，并對其余的極大平面圖提出了一個猜想，若這個猜想成立，則可以證明極大平面圖