圖的子圖和染色

《圖的子圖和染色》是依託山東大學，由王光輝擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖的子圖和染色
• 項目類別：青年科學基金項目
• 項目負責人：王光輝
• 依託單位：山東大學

中文摘要

圖的匹配、路和圈結構是圖論中的基礎而又重要的研究方向，也是圖的因子理論，極值圖論和Ramsey理論的研究重點。圖的染色問題也是圖論中的熱門的研究課題。本課題主要研究圖的子圖和圖的染色的關係，其中包括圖的正交匹配和邊染色圖中的彩色匹配的關係，邊染色圖中的彩色圈和正常染色的圈的存在性問題，圖的Ramesy數和anti-Ramsey數，以及有向圖中的彩色路問題等。我們力求解決上述研究領域的幾個難題和猜想，改進關於邊染色圖中的匹配、路和圈的存在性條件，深入刻畫邊染色圖中的子圖和染色之間的關係。本課題的研究涉及到矩陣理論，組合設計，超圖理論等多個領域，問題的解決對計算機科學，生物數學及組合數學和圖論的理論發展和創新都有非常重要的意義。

結題摘要

圖的多色子圖方面,我們得到了圖的彩色匹配存在的色度條件，而且我們對圖的正交匹配特別是Alspach猜想做了研究，得到了目前該問題的最好的界。同時，我們對Erdös-Bollobás關於邊染色圖中的正常染色圈的下界做了改進，得到了目前最好的界，為我們後續關於超圖中的極值問題（特別是彩色匹配）打下了很好的基礎。另外，我們對圖的和可區別染色、圖的無圈邊染色等也做了研究。在對圖的和可區別染色的研究中，我們除了藉助於傳統的discharging方法，還套用組合零點定理，結合MATLAB的計算，使我們在對一般圖、平面圖和幾類特殊圖的研究中分別取得了不錯的結果。在對無圈邊染色的研究中，利用熵壓縮的方法，在推廣的無圈邊染色方面取得了一系列不錯的成果。共發表SCI論文30餘篇，多次在國內和國際會議上作報告。前三位申請人也都在此基礎上獲得了國家自然科學基金的資助。