《關於幾類圖的分數色數與獨立數》是依託華中師範大學，由胡小蘭擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：關於幾類圖的分數色數與獨立數
- 項目類別：青年科學基金項目
- 項目負責人：胡小蘭
- 依託單位：華中師範大學
項目摘要,結題摘要,
項目摘要
圖的染色理論是圖論研究的一個熱點，它在組合最最佳化、交通流、網路設計和計算機理論等方面有著廣泛的套用。頂點染色是圖的染色理論中的一個主要內容，分數染色是頂點染色的一種推廣。由於圖的分數色數是頂點色數的一個下界，研究圖的分數色數對於我們更進一步地研究圖的頂點色數有著重要的意義。此外，由於圖的獨立數不小於其階數與分數色數的比值，我們可以通過研究圖的分數色數，來研究圖的獨立數。圖的獨立數與Ramsey理論有著緊密的聯繫。本項目擬採用權轉移、線性規劃、組合和機率等方法研究與三色問題有關的分數染色與最大獨立集問題，不含4圈的(平面)圖的獨立數與4圈對完全圖的(平面)Ramsey數，不含K5細分的圖的分數色數與獨立數。這些問題的解決，不僅可以從另一角度推進三色問題的驗證工作，而且可以改進4圈對完全圖的(平面)Ramsey數的界，推廣平面圖的分數染色的結果，從而豐富和完善圖的染色理論和Ramsey理論。
結題摘要
本項目中，通過構造一個(4:1)-可選的但不是(8:2)-可選的圖，否定了Erdős-Rubin-Taylor猜想(每個(a:b)-可選圖都是(ka:kb)-可選的)。通過對圖的結構性質的刻畫，利用圖的hyperbolicity理論證明了任意給定曲面Σ上只存在有限多個圍長為5的(3a:a)-臨界圖，推廣了Thomassen等人的工作。在此基礎上，證明了對於最大度為Δ，圍長為5的平面圖G，存在M∆，使得其分數色數不超過3-3/(2M∆+1)。在分數染色方面，我們還證明了不含4圈或5圈的平面圖是(11:3)-可選的，從而其分數色數不超過11/3，獨立數至少為3|V(G)|/11；不含4圈或6圈的平面圖(7:2)-可染的，從而其分數色數不超過7/2，獨立數至少為2|V(G)|/7。圖的限制條件的染色問題方面，用顏色交換的技術確定了圖的鄰點可區別全色數新的上界；通過刻畫2-退化圖的子圖結構，確定了其鄰和可區別邊色數。結合極值圖論的方法，證明了當圖的獨立數為2時，Erdős-Sós猜想和Loebl-Komlós-Sós猜想成立；確定了4圈對樹的平面Ramsey數；證明了毛毛蟲的燃燒數的上界，確定了幾類特殊毛毛蟲的燃燒數。針對網路圖的結構，研究了某些具有套用背景的網路的容錯性和匹配性。
