1、圖的著色問題來源于圖論中最著名的四色猜想，它是圖論中的一個重要分支。圖的著色理論不僅在離散數學與組合分析等數學理論中有應用，它在最優(yōu)化、交通運輸、通訊網絡和計算機理論等方面也有著廣泛的應用。生活中安排會議或考試的日程以避免沖突，以及安排化學藥品的存儲以避免相互反應等具體問題也都可以用圖的著色理論來解決。基于圖的著色理論有著重要的理論意義和實用意義，圖的著色問題一直是圖論研究中的熱點問題。
　　 本文主要研究了平面圖的3著色與線性

2、著色。它們都是針對圖中的頂點進行著色的，其中線性著色以正常頂點著色為基礎，3著色即只用了3種顏色的正常頂點著色。主要內容可分為四部分：
　　 第一部分(第一章)主要介紹了圖論中著色問題的歷史背景，以及本文的研究目的與主要內容。
　　 第二部分(第二章)介紹了圖的著色中的一些基本概念，重點介紹了正常頂點著色和線性著色的概念，并對兩種著色的研究現狀進行了綜述。
　　 第三部分(文章的三、四章)是本論文的核心部分。在這

3、一部分中，探討了平面圖的3著色和線性著色問題。第三章首先通過分析全由3度頂點構成的偶圈的結構，發(fā)現運用著色技巧可以實現著色延拓，給出了一個引理來說明最小反例圖的結構；然后通過對歐拉公式作適當變形，巧妙設計權值分配規(guī)則，給出了平面圖3可著色的3個充分條件。第四章中通過分析平面圖的結構，結合線性著色的特點，運用已知引理在一定程度上縮小了平面圖線性著色色數的上界。
　　 第四部分(第五章)總結了本文研究所得到的結論，指出了本文的創(chuàng)新之