《關於圖染色的x-有界猜想及相關問題研究》是依託南京師範大學，由許寶剛擔任項目負責人的面上項目。
基本介紹
- 中文名：關於圖染色的x-有界猜想及相關問題研究
- 項目類別：面上項目
- 項目負責人：許寶剛
- 依託單位：南京師範大學
項目摘要,結題摘要,
項目摘要
圖論是離散數學的一個重要分支，而圖的染色理論和子圖結構問題一直以來都是圖論研究的核心問題。強完美圖定理是本世紀最重要的圖論研究成果之一，證明了如果一個圖既不含長度至少為5 的奇圈又不含其補圖做為導出子圖，則該圖的色數與團數相等。Gyarfas (1975) 和 Sumner (1981) 各自獨立地提出了以下猜想（我們稱之為 x-有界猜想）：任意給定一棵樹 T，存在一個函式 f，使得當一個圖 G 不含 T 做為導出子圖時，x(G)≤f(w(G))，其中 x(G) 和 w(G) 分別表示 G 的色數和團數。x-有界問題是完美圖問題的延伸與推廣，是目前國際圖論界最為關注的問題之一，有重要的理論意義和套用價值，我們將圍繞這一猜想和相關問題展開研究。
結題摘要
圖論是離散數學的一個重要分支，而圖的染色理論和子圖結構問題一直以來都是圖論研究的核心問題。強完美圖定理是本世紀最重要的圖論研究成果之一，證明了如果一個圖既不含長度至少為5 的奇圈又不含其補圖做為導出子圖，則該圖的色數與團數相等。Gyarfas (1975) 和 Sumner (1981) 各自獨立地提出了以下猜想（我們稱之為 x-有界猜想）：任意給定一棵樹 T，存在一個函式 f，使得當一個圖 G 不含 T 做為導出子圖時，x(G)≤f(w(G))，其中 x(G) 和 w(G) 分別表示 G 的色數和團數。x-有界問題是完美圖問題的延伸與推廣，是目前國際圖論界最為關注的問題之一，有重要的理論意義和套用價值. 我們在 Gyarfas-Sumner x-有界猜想及色數與禁用導出圈關係方面取得了一些新結果，我們還在圖的劃分問題上取得了一些進展。
