《圖的列表染色及相關問題研究》是依託浙江師範大學，由陳敏擔任項目負責人的面上項目。
基本介紹
- 中文名：圖的列表染色及相關問題研究
- 項目類別：面上項目
- 項目負責人：陳敏
- 依託單位：浙江師範大學
項目摘要,結題摘要,
項目摘要
圖的染色理論在圖論研究領域中一直占據著重要的地位，在信息科學、通訊科學、運籌學等領域有著廣泛的套用，受到了國內外同行的密切關注。本項目旨在圍繞幾類圖染色猜想，研究當前國際圖論界的熱點問題。首先，力爭解決或部分解決BFKRS和MRW兩大關於平面圖無圈點列表染色猜想。其次，刻畫具有點蔭度為2的平面圖類。然後，研究平面圖列表(1,1,1)-染色，擴大滿足Xu-Zhang猜測的圖類，討論具有圍長限制的平面圖和稀疏圖的(i,j,k)-可染性。再有，在現有的基礎上，爭取徹底解決極具挑戰的Sanders-Zhao邊面染色猜想，推廣平面圖邊面（列表）染色的一些結果到曲面圖上去。最後，探討其他一些染色問題，如星染色、點面染色和完備染色。改進平面圖的星色數上界與下界，研究平面圖6-點面列表染色猜想，精確求出某些特殊平面圖的完備列表色數。擬在四年內完成學術論文20餘篇，其中15以上發表在SCI源期刊上。
結題摘要
圖的染色理論在圖論研究領域中一直占據著重要的地位，在信息科學、通訊科學、運籌學等領域有著廣泛的套用，受到了國內外同行的密切關注。本項目主要研究圖的頂點列表染色（包括正常、非正常、無圈、限制性列表染色）、分解問題（蔭度、頂點列表蔭度、森林分解）以及邊面染色等熱點問題。研究圍繞著相關領域的幾個著名猜想（如Sanders-Zhao 猜想、Xu-Zhang 猜想、無圈頂點列表染色猜想）展開，致力於解決或部分解決這些猜想和難題，給出相關圖參數好的上界或下界，對特殊圖族（如平面圖、環面圖、稀疏圖等）給出若干參數的精確值。解決了Sanders-Zhao 猜想剩餘的兩種情形之一，即證明了最大度為5的平面圖是邊面7-可染的。完全刻畫了環面圖列表頂點蔭度。部分解決了MRW提出的關於平面圖是無圈4-點列表可染的猜想。研究了列表頂點蔭度至多為2的環面圖類。找到了新的圖類滿足Xu-Zhang 猜想。給出了平面圖3-點列表可染性以及4-點列表可染性的充分條件。對圍長為5的平面圖類，將已知的子圖分解結果全部改進到森林分解。證明了九龍樹猜想對k≤2的情形成立，此結果發表在Journal of Combinatorial Theory, Series B期刊上。四年內共發表掛有基金號的學術論文17篇，其中SCI檢索15篇。
