圖的無圈染色和存活率研究

《圖的無圈染色和存活率研究》是依託浙江師範大學，由王維凡擔任項目負責人的面上項目。

基本介紹

• 中文名：圖的無圈染色和存活率研究
• 項目類別：面上項目
• 項目負責人：王維凡
• 依託單位：浙江師範大學

項目摘要

圖的染色是圖論研究的重要內容,在現代計算機科學、信息科學、管理科學等領域有著十分廣泛的套用，一直得到國內外同行的極大關注。圖的存活率是一個新引進的圖參量，在森林防火、疫情控制、計算機防毒等實際問題中有著很強的套用背景。本項目從圖的結構性質入手，研究圖的各種染色問題，如無圈點染色、無圈邊染色、線性染色、星染色、列表染色等。力爭解決或部分解決Borodin等人提出的關於平面圖是無圈5-可選的猜想；圍繞Alon-Sudakov-Zaks猜想，對一般圖改進已知無圈邊色數的上界，找到新的圖類滿足該猜想。研究圖的防火問題，找出存活率漸近為正的新的更廣泛的圖類，回答是否絕大部分的圖的存活率漸近為0的問題，推廣防火問題到有向圖上。研究超立方體網路、Star 等一些著名網路的距離標號數，爭取改進已有的結果。擬在三年內完成學術論文20餘篇，其中10篇以上發表在SCI雜誌上。

結題摘要

圖的染色、標號與存活率是圖論研究的重要內容, 在現代計算機科學、信息科學、管理科學等領域有著十分廣泛的套用，近些年來得到了國內外同行的高度重視。本項目從圖的結構性質入手，研究圖的各種染色與標號問題，如無圈染色、鄰點區別邊染色和全染色、平面圖的各種全染色、存活率等。證明了4-正則圖、沒有3-圈、4-圈、5-圈、或6-圈的平面圖等滿足著名的Alon-Sudakov-Zaks無圈邊染色猜想，對平面圖的無圈邊色數的上界從△+12改進到△+7。證明了最大度為6的平面圖是8-邊-面可染的，最大度至少為9的平面圖是(△+2)-完備可染的，特別是徹底解決了著名的Kronk和Mitchem關於平面圖完備染色猜想，即證明了：每個平面圖是(△+4)-完備可染的。對一般圖給出鄰點區別邊色數和全色數好的上界，刻畫了外平面圖、大圍長平面圖、有較小最大平均度的圖的鄰點區別邊色數和全色數。給出圖的存活率的新概念，建立一些稀疏圖的存活率的下界，特別是證明了平面圖的3-存活率大於一個正的常數。立項以來，項目組成員在國內外學術刊物上發表論文 60 篇，其中被 SCI 檢索 45 篇，獲得浙江省自然科學學術獎一等獎1項和浙江省科學技術二等獎1項。