《有約束條件的圖染色問題研究》是依託浙江師範大學，由王維凡擔任項目負責人的面上項目。
基本介紹
- 中文名：有約束條件的圖染色問題研究
- 項目類別：面上項目
- 項目負責人：王維凡
- 依託單位：浙江師範大學
項目摘要,結題摘要,
項目摘要
圖的染色是圖論研究的重要內容,在現代計算機科學、信息科學、管理科學等領域有著十分廣泛的套用，一直得到國內外同行的極大關注。本項目從圖的結構性質入手，研究圖的各種約束染色問題，如無圈點染色、無圈邊染色、線性染色、列表染色、鄰點區別邊染色、鄰點區別全染色等。力爭解決或部分解決Borodin等人提出的關於平面圖是無圈5-可選的猜想；圍繞Alon-Sudakov-Zaks猜想，對一般圖改進已知無圈邊色數的上界，找到新的圖類滿足該猜想。特別地，力爭給出平面圖的無圈邊色數緊的上界，刻畫有大圍長的平面圖的無圈邊色數。研究圖的鄰點可區別邊染色和全染色，改進一般圖鄰點可區別邊色數和全色數的上界，並對最大度較大的平面圖刻畫這兩個參數。此外，研究圖的控制數、圖的能量、一些著名網路圖的路和圈的嵌入問題等，爭取改進已有的結果。擬在四年內完成學術論文30餘篇，其中20以上發表在SCI雜誌上。
結題摘要
圖的染色是圖論研究的重要內容,在現代計算機科學、信息科學、管理科學等領域有著十分廣泛的套用，一直得到國內外同行的極大關注。本項目從圖的結構性質入手，研究圖的各種染色問題（鄰點區別邊染色、鄰點區別全染色、無圈染色、列表染色等）。部分解決了Borodin等人提出的關於平面圖是無圈5-可選的猜想。找到了新的圖類滿足Alon-Sudakov-Zaks關於無圈邊染色的猜想，建立了平面圖的無圈邊色數緊的上界，刻畫了圍長較大的平面圖的無圈邊色數。改進了一般圖鄰點區別邊色數和全色數的上界，並對高度平面圖確定了這兩個參數。證明了平面圖是3-好的和有向平面圖是2-好的。研究樹和哈林圖的L(2,1)-標號與(2,1)-全標號，改進了一些已有結果。此外，研究圖的蔭度、控制數、圖的能量、經典網路圖的路和圈的嵌入問題等。四年內發表學術論文85篇，其中被SCI檢索63篇。
