《關於圖染色及相關問題研究》是依託浙江師範大學，由卜月華擔任項目負責人的面上項目。
基本介紹
- 中文名：關於圖染色及相關問題研究
- 項目類別：面上項目
- 項目負責人：卜月華
- 依託單位：浙江師範大學
項目摘要,結題摘要,
項目摘要
圖的染色及其在相關學科中的套用一直是圖論研究的熱點，是推動組合數學和理論計算機科學向前發展的源動力之一，屬組合數學、算法設計與分析及通迅領域的交叉學科。本項目主要研究圖的染色理論及圖論在通迅網路中的套用。用權轉移方法研究一類平面圖和曲面圖的結構性質，從而探討這些圖類的3-可染問題、均勻(列表)染色、各種意義下的均勻全染色點可區別染色和星染色，圍繞著名的Steinbergr關於3-可染猜想和Kostochka等的均勻列表染色猜想展開重點研究，進一步擴展滿足這些猜想的圖類；用最大平均度、圍長等參數來刻劃平面圖、低度圖等稀疏圖的星色數；用機率方法估計階數充分大的圖的均勻（全）色數和點可區別色數；考慮一些著名網路的限制容錯嵌入性質並設法確定其可靠性參數（如超連通度、堅韌度等），並對容錯嵌入和參數估計作算法分析。本項目擬在三年內完成學術論文20餘篇。其中一半以上發表在SCI雜誌上。
結題摘要
本項目主要研究圖的染色理論、連通性問題、圖的控制數及其圖的頻寬、割寬等問題。用一次或多次權轉移方法研究一類平面圖的結構性質，從而探討這些圖類的3-可染問題、均勻(列表)染色、星染色、BB-染色和圖的標號。對於均勻（列表）染色，我們主要圍繞Meyer等提出的均勻列表染色猜想展開研究，證明了外平面圖、2-退化圖和圍長至少為6的平面圖均勻列表染色猜成立,同時給出了一些不含特殊圈的平面圖均勻（列表）染色數的界。對於圖的BB-染色，我們主要討論了含奇圈但不含若干特殊短圈的連通平面圖關於生成樹的BB-染色，同時也給出了一些特殊的圖類，如Halin圖、偽Halin圖、完全圖、輪等關於生成樹和Hamilton路的BB-染色問題。對於平面圖的全染色問題，研究了以最大度和不含若干特殊短圈為條件，討論了幾類平面圖的全可染性問題，給出了若干平面圖的列表全色數等於全色數的充分條件。對於平面圖的 -標號問題，主要圍繞著名的Wegner猜想展開研究，證明了對於圍長至少為6的平面圖，Wegner猜想成立，得到了不含4-9圈的平面圖的 -標號、圍長至少為6的平面圖的 -標號、最大度至多為6的的平面圖的 -標號等，同時給出了若干不含某些特殊短圈的平面圖的 -標號的界。對於平面圖的3-（列表）染色問題，首先研究了關於沒有4種長度短圈的平面圖的頂點3-染色和列表3-染色，在前人工作的基礎上，基本完成了兩個階段性的研究成果，即沒有4，i，j，k-圈（4）
