《運用權轉移方法研究平面圖的若干染色問題》是依託浙江師範大學，由陳敏擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：運用權轉移方法研究平面圖的若干染色問題
- 項目類別：青年科學基金項目
- 項目負責人：陳敏
- 依託單位：浙江師範大學
項目摘要,結題摘要,
項目摘要
圖的染色是圖論研究的重要內容，在現代計算機科學、信息科學等領域有著十分廣泛的套用，一直得到國內外同行的極大關注。而平面圖的染色問題一直是圖論界的熱點與難點。自Appel與Haken運用Discharging方法證明了四色定理後，Discharging方法在平面圖的研究中起到了非常重要的作用。本項目主要運用此方法來研究平面圖的無圈染色、星染色以及邊面染色。首先探討無圈點列表色數與圈長之間的關係，找到更多的平面圖類滿足Borodin等人提出的關於平面圖是無圈5-點列表染色的猜想。其次通過研究圖的星染色，爭取給出平面圖緊的上界，完整刻畫具有較小最大度圖的星色數；最後力爭解決Sanders-Zhao提出的平面圖邊面全染色猜想。同時研究可嵌入高維曲面（如環面、仿射平面）圖的邊面全染色問題，推廣平面圖邊面全染色的一些結果到曲面圖上去。擬在三年內發表8篇左右被SCI檢索的期刊論文。
結題摘要
圖的染色是圖論研究的重要內容，在現代計算機科學、信息科學等領域有著廣泛的套用，近年來得到國內外同行的高度重視。本項目主要運用Discharging方法來研究圖的無圈點列表染色、星列表染色、邊面染色、點蔭度以及非正常頂點列表染色。證明了不包含4-圈相鄰於長度為3,4,5,6-圈平面圖是無圈6-點列表可染的。給出了當前滿足Montassier-Raspaud-Wang無圈4-點列表染色猜想的最好結果，即：證明了不包含4-圈和5-圈的平面圖是無圈4-點列表可染的。研究了稀疏圖的星列表色數。證明了環面Subcubic圖的星列表色數至多為6，並通過例子說明上界6是最優的。證明了最大度為4或5的極大平面圖滿足Sanders-Zhao邊面染色猜想，刻畫了最大度為6的哈林圖的邊面列表色數。徹底解決了Raspaud-Wang點蔭度猜想，提供了滿足平面圖列表(1,1,1)-染色猜想的若干充分條件。立項以來，項目組成員在國內外學術刊物上發表SCI論文9篇，獲得浙江省自然科學學術獎一等獎1項和浙江省科學技術二等獎1項。
