多項式方法在圖論中的套用

《多項式方法在圖論中的套用》是依託浙江師範大學，由朱緒鼎擔任項目負責人的面上項目。

基本介紹

• 中文名：多項式方法在圖論中的套用
• 項目類別：面上項目
• 項目負責人：朱緒鼎
• 依託單位：浙江師範大學

項目摘要

多項式方法在組合學和數論中有廣泛地套用。本項目將研究多項式方法在圖論研究中的套用，包括在圖的anti-magic標號、列表染色、線上列表染色和圖的點邊賦權的研究中的套用。主要關注幾個長期未解決的猜想，如anti-magic標號猜想：每一個連通的不等於K2的圖存在anti-magic標號，（1,3）-點邊列表賦權猜想：每個不含孤立邊的圖是（1,3）-列表可選的（該猜想可推出1-2-3猜想）：每個不含孤立邊的圖有一個用1,2,3權重的邊賦權使得相鄰頂點的權重和不等。我們還將研究一些圖類的線上選擇數，以及圖的染色和列表染色。在套用多項式方法於這些問題的同時，進一步發展這一方法。

結題摘要

多項式方法是圖論研究的重要工具，本項研究計畫一個要點是套用多項式方法於一些具體的圖論問題以及研究多項式方法的推廣。另一個要點是研究圖的各類染色問題。本項目圍繞上述方向，針對計畫提出的問題開展研究。主要成果有：（1）證明平面圖的Alon-Tarsi數最大為5。這一結果強化了Thomassen關於平面圖5-可選的經典結果，解決了有Hefetz在《Journal of Combinatorial Theory Ser. B》上提出的公開問題（2）證明了每一個平面圖G都含有一個匹配M, G-M的Alon-Tarsi數不超過4。這一結果推廣了Cushing-Kierstead關於平面圖1-defective 4-可選的結果，解決了平面圖均可1-defective 線上4-可選的問題。這一問題Kierstead團隊和我們都研究多年。（3）提出了augment rooted tree的概念，構造性證明了大圍長augmented tree的存在性。Erdos利用機率方法證明了大色數大圍長圖的存在性。這是色數圖論的經典結果。利用大圍長augmented tree，我們給出了這一結果非常簡潔的構造性證明，同時構造了大選擇數大圍長稀鬆二部圖。Alon利用組合零點定理證明平均最大度數為2k-2的二部圖是k-可選的。出乎人們意料，我們證明這一有關邊數的條件是最優的。（4）研究了列表染色的精細化問題，提出了lambda-可選的概念，(k+epsilon)-可選的概念，廣義符號圖染色的概念和強分數選擇數的概念。證明了平面圖的最大強分數選擇數不小於4+2/9， 無三角形的平面圖的最大強分數選擇數不小於3+1/17。 證明了每一個平面圖都是 （4+1/2）-可選的。（5）研究了列表染色的一個推廣-DP染色。研究了分數DP-色數的概念。刻畫了分數DP-色數為2的圖。證明了當頂點個數足夠接近色數是，其DP-色數等於色數。得到了滿足這一結論的頂點數的上界的級別（確切數仍然是一個未解決的問題）。本項目也協助主辦大型學術會議一次，中小型學術會議四次。邀請十多位學者來訪，積極出訪交流。培養學生方面，有四位博士生，十位碩士生參與項目的研究。