《幾類圖染色問題的研究》是依託福州大學，由侯建鋒擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：幾類圖染色問題的研究
- 依託單位：福州大學
- 項目類別：青年科學基金項目
- 項目負責人：侯建鋒
項目摘要,結題摘要,
項目摘要
圖的染色問題一直是圖論研究的熱門問題之一, 其研究對圖論的發展有著重要的理論意義, 並且在Hessin矩陣的計算、數據傳輸、大規模積體電路的設計、網路最佳化等方面有著重要的套用價值. 本項目主要研究圖染色理論中幾個熱點問題, 其中包含全染色、列表染色、無圈染色、f-染色等. 力求解決上述染色中的幾個基本問題, 並且確定某些特殊圖的全色數、列表色數、無圈邊色數、f-色數等, 解決圖染色問題中幾個著名的猜想, 利用無圈染色計算Hessian矩陣, 設計上述染色的多項式時間算法, 將其套用在網路設計和大規模積體電路最佳化上. 本項目所研究的問題是圖的染色理論中經典的問題, 內容涉及圖論、規劃論、矩陣論、機率論、組合拓撲等領域. 問題的解決對圖的染色理論、矩陣分解和網路最佳化的發展有較大的促進作用.
結題摘要
圖的染色問題一直是圖論研究的熱門問題之一, 其研究對圖論的發展有著重要的理論意義, 並且在Hessin矩陣的計算、數據傳輸、大規模積體電路的設計、網路最佳化等方面有著重要的套用價值. 本項目主要研究了圖的無圈染色、全染色、線性蔭度等, 給出了平面圖無圈邊色數新的上界, 研究了圍長較大的平面圖的無圈邊染色, 給出了其無圈邊色數, 給出了含有三角形的平面圖無圈邊色數的上界, 驗證了特殊情形下的無圈邊染色猜想, 用機率方法研究了圍長較大的圖的無圈邊染色. 線上性蔭度方面取得重要進展, 得到了最大度至少是9平面圖的線性蔭度. 在全染色面, 主要考慮不含短圈的平面圖的全染色, 給出其全色數, 改進了原有結果.
