圖的標號及相關問題研究

《圖的標號及相關問題研究》是依託浙江師範大學，由卜月華擔任項目負責人的面上項目。

基本介紹

• 中文名：圖的標號及相關問題研究
• 項目類別：面上項目
• 項目負責人：卜月華
• 依託單位：浙江師範大學

項目摘要

圖的染色、標號及其套用一直是圖論研究的重要內容之一，其研究富有挑戰性，在網路最佳化、網路頻率分配、算法設計和大規模積體電路設計等方面有重要套用。本項目主要研究圖的染色理論、標號理論及圖論在其它學科中的套用等問題。套用權轉移技術和多項式理論研究在平均度或短圈限定條件下平面圖的結構性質，從而探討這些圖類的3-可染（可選）問題及形如(m,d)*-（列表）染色、BB-（列表）染色、 L(p,q)-標號、對局標號等，以解決或部分解決Wegner關於平面圖的L(1,1)-猜想和Steinberg 關於3-染色猜想為主攻目標；用機率方法及矩陣理論構造若干特殊圖以確定相應的色數；探討若干染色的算法複雜性問題。本項目所研究的問題一部分是國際著名學者提出的一些問題， 一部分問題是我們首次提出的，內容涉及到圖論、組合最佳化、算法複雜性等領域。

結題摘要

本項目主要研究圖的染色理論、圖的譜半徑及拓撲指數等問題。用權轉移方法研究一類平面圖的結構性質，從而探討這些圖類的非正常（列表）染色問題、injective（列表）染色問題、BB-列表染色問題、L(p,q)-標號與對局染色問題。對於非正常（列表）染色，我們針對平面圖的3-（可選）可染問題，考慮稍弱的非正常（列表）染色，證明了不含4-圈和6-圈的平面圖是（1,1,0）-可染的；不含4,i,j-圈(部分i,j); 4