《邊染色臨界圖的相關問題的研究》是依託中國礦業大學，由苗連英擔任項目負責人的面上項目。
基本介紹
- 中文名：邊染色臨界圖的相關問題的研究
- 項目類別：面上項目
- 項目負責人：苗連英
- 依託單位：中國礦業大學
項目摘要,結題摘要,
項目摘要
P.G.Tait證明四色猜想等價於任一2-邊連通立方平面圖的邊都可以用三種顏色正常染色，由此產生了圖的邊染色的概念。由於它的重要的理論意義和廣泛的套用背景，圖的邊染色理論已成為圖論的一個重要分支，而在圖的邊染色研究中臨界圖起著很重要的作用。本項目的研究主要圍繞臨界圖的相關問題而展開。. 首先在Vizing鄰接引理的基礎上，進一步研究一般臨界圖和平面臨界圖的的性質。研究2-邊連通的最大度是3的平面圖的分類問題，對於至少有3個2-點的情況證明M.O.Albertson的猜想為真；利用discharging方法研究臨界圖的平均度，證明其平均度接近其最大度減一；利用歐拉公式和discharging方法研究平面圖的分類，證明最大度是6的平面圖都是第一類的；利用一般圖存在1-因子或幾乎1-因子的條件給出臨界圖存在1-因子或幾乎1-因子的充分條件。
結題摘要
起源於四色猜想的圖的染色理論和圖的拓撲指數以及圖的控制理論是圖論的重要研究分支，具有重要的理論價值和套用背景。在國家自然基金項目(No.11271365)的資助下，本項目主持人和項目組成員的研究工作主要圍繞以下方面展開：關於邊染色臨界圖的若干猜想、圖的距離染色、圖的動態染色和r-hued染色、圖的無圈點染色、平面圖的強邊染色、1-平面圖的無圈邊染色和點染色、圖的離心距離和以及圖的若干控制參數。得到如下結果： 1、給出了邊染色臨界圖的一些新性質，利用這些新性質改進了最大度為11或12的臨界圖的平均度的下界。2、研究了Vizing的關於臨界圖的獨立數的猜想，改進了Woddall的關於獨立數上界的結果。3、關於圖的動態染色和r-hued染色，研究了圖的動態色數與其去掉一條邊或一個點後的動態色數之間的關係，給出了它們之差的上下界並刻劃了極圖；給出了K4-minor free 圖的r-hued色數的一個緊的上界和r-hued列表色數的一個上界；證明了對於圍長至少是5的平面圖G，當r是3到7之間的整數時，G的r-hued色數不超過r+11。4、關於平面圖的強邊染色，給出了圍長和最大度至少是5的平面圖的強邊色數的一個上界。5、關於1-平面圖的無圈邊染色和點染色，給出了無三角形的1-平面圖的無圈邊色數的一個上界，並且證明了無4-圈或相鄰5-點的1-平面圖都是5-可染色的。6、關於圖的無圈點染色，證明了最大度是6的圖都是無圈10-可染色的，改進了Hervé Hocquard （2011）的主要結果。7、關於圖的離心距離和，刻畫了給定最大度的具有最大EDS的樹，刻畫了控制數是3的具有最大EDS的樹，刻畫了給定獨立數的具有最大和最小EDS的樹，刻畫了給定匹配數的具有最大EDS的樹。8、對於圖的控制問題，給出了尋找塊圖和一些特殊樹的2-step控制集的O（m）次算法；給出了完全二部圖和輪圖的符號全控制數的精確值；證明了邊全控制問題對於最大度是3的平面圖、無向路圖、一些弦圖和一些樹是NP-完備的等等。9、研究了二氧化碳排放現狀，為制定應對氣候變化國家方案及實現我國二氧化碳減排目標提供決策與對策參考；構建我國霧霾污染治理控制機制，為我國的大氣污染治理提出具有科學性和可操作性的對策建議。
