《幾類圖的結構與染色問題》是依託西安電子科技大學，由張欣擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：幾類圖的結構與染色問題
- 項目類別：青年科學基金項目
- 項目負責人：張欣
- 依託單位：西安電子科技大學
中文摘要,結題摘要,
中文摘要
圖的結構與染色問題是圖論中基礎而重要的研究方向，其具有眾多的理論成果和廣泛的套用背景。本項目圍繞圖論中幾個經典的猜想，利用權轉移方法、機率方法等數學方法與規劃論等數學工具研究1-平面圖、(d,1)-平面圖、IC-平面圖、偽外平面圖、IC-外平面圖與雙外平面圖等幾類圖的結構與染色問題,其中包括它們的輕子圖的存在性、子式理論、判定算法以及邊染色、全染色、列表邊（或全）染色、無圈點（或邊）染色、均勻點染色、關聯染色與博弈染色等，力求在1-平面圖及其子類的層面上解決或部分解決上述研究領域中的難題或猜想，並探索上述幾類拓撲圖的結構與染色問題在現實生活中的套用價值。此外，上面提及的(d,1)-平面圖、IC-外平面圖與雙外平面圖是本項目首次提出的，這裡將對其做開創性的理論研究。本項目涉及到圖論，規劃論，機率論，組合拓撲等眾多數學領域，問題的解決對理論計算機科學與圖論的理論發展有著較大的促進作用。
結題摘要
圖的結構與染色問題是圖論中基礎而重要的研究方向，其具有眾多的理論成果和廣泛的套用背景。本項目主要對於1-平面圖及其幾個重要子類，如NIC-平面圖、IC-平面圖、平面圖與外1-平面圖等的結構與染色問題做具體的研究。在結構方面，主要研究特定圖類中的輕子圖的存在性，以及在某種染色意義下的可約結構的存在性，證明了最小度至少為6的1-平面圖、最小度至少為5且最小邊度至少為12的1-平面圖、最小度至少為5的NIC-平面圖都含有一個輕3-圈，並給出了它的height與weight值的較好的上界，同時給出了NIC-平面的完全多部圖與IC-平面的完全多部圖的完整刻畫。在染色方面，主要是圍繞染色圖論中的一些經典的定理與猜想，如邊染色Vizing定理、全染色猜想、列表染色猜想、全標號猜想等，確定圖的相關染色參數的（相對較好的）上界，或者驗證相關猜想。例如，本項目給出了外1-平面圖具有第一類邊色數的充分必要條件，以及最大度為8的平面圖的全色數是9的一些充分條件，證明了全染色猜想對於外1-平面圖成立並給出了外1-平面圖具有第一類全色數的幾個充分條件，證明了列表染色猜想對於最大度至少為5的外1-平面圖與最大度至少為8且不含相鄰的4-圈的平面圖成立，證明了(2,1)-全標號猜想對於最大度至少為12的平面圖成立，提出了群邊染色的概念以及群邊染色猜想並對於圍長至少為4Δ/(Δ-2)的平面圖證明了該猜想。本項目的另一個研究主題是圖的均勻點染色。首先，圍繞均勻正常點染色方面的兩個著名猜想：均勻Δ-染色猜想與Chen-Lih-Wu猜想，本項目對於1-平面圖及其子類的均勻染色數與均勻染色閥值做系統的研究，證明了上述兩個猜想對於最大度至少為15、13、12、3的1-平面圖、NIC-平面圖、IC-平面圖、外1-平面圖成立。除此之外，本項目對於圖的r-均勻正常點染色也做了一定的研究，得到了一些有意義的結論。另一方面，本項目圍繞圖的均勻點蔭度猜想，得到了一些圖類的均勻點蔭度的好的上界，證明了均勻點蔭度猜想對於最大度至少為|G|/2的圖或者最大度至多為3的圖成立，給出了平面圖的均勻點蔭度至多為3的充分條件，提出了均勻列表點蔭度猜想，並證明了該猜想對於最大度至少為8的平面圖成立。本項目涉及到圖論，規劃論，機率論，組合拓撲等眾多數學領域，問題的解決對理論計算機科學與圖論的理論發展有著較大的促進作用。
