圖的群染色的研究

《圖的群染色的研究》是依託中國人民大學，由李昊擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：圖的群染色的研究
• 項目類別：青年科學基金項目
• 項目負責人：李昊
• 依託單位：中國人民大學

項目摘要

本項目研究圖的群染色性質及相關問題，主要研究群染色性質與群結構是否存在依賴關係，包括阿貝爾群和非阿貝爾群染色的區別和元素個數相同但不同構的群在染色上的等價關係；利用隨機方法來研究群染色，主要包括在Erd?s-Rényi模型上刻畫群染色與群列表染色以及利用Lovász局部引理研究多部圖，特別是完全二部圖的群染色情況；研究多重圖與簡單圖的群染色性質的不同，重點關注多重平面圖的群染色數與極圖; 研究群完美圖的結構，特別是線圖和無爪圖的群完美性。這些問題從算法上來講，都是論是π2p -完全的，比NP-完全的(NP-complete)問題需要更多的計算和時間。因此是具有重要的理論意義和實際意義。它的研究將加深圖的結構和參數研究，對群論、網路最佳化、密碼學及計算機理論等方面也具有重要的理論價值。

結題摘要

染色問題是圖論中一個重要的領域，擁有大量的難題和猜想。群染色是一般染色的一個推廣。在項目研究中，我們研究了多重圖的群染色問題，得到了多重圖群染色版本的Brooks定理。我們同時對r-色調染色和(r,s)-正常圖進行了研究。我們確定了無爪圖的3色調染色數和列表3-色調染色數的上界。這表明除了一些無爪圖是(3,4)-正常圖外，其他所有的無爪圖都是(3,3)-正常圖。線圖是研究圖的結構時經常使用的方法。求一個圖的線圖可以看成一種作用在圖上的運算。研究表明，大多數圖的線圖具有比原圖更好的哈密頓性質。我們確定了圖的泛圈連通因子，也就是最小的整數k，使得對圖做k次線圖運算，得到的圖是泛圈連通的。在研究圖的密度和利用線圖研究圖的哈密頓性質的時候，摺疊圖和超歐拉圖是最常使用到的圖類。我們將他們擴展到s摺疊圖和寬度為s的超歐拉圖，並且證明了出類似摺疊圖的性質和定理，推廣了摺疊圖的方法。