圖的圓環染色和分數染色

《圖的圓環染色和分數染色》是依託浙江師範大學，由朱緒鼎擔任項目負責人的面上項目。

基本介紹

• 中文名：圖的圓環染色和分數染色
• 項目類別：面上項目
• 項目負責人：朱緒鼎
• 依託單位：浙江師範大學

項目摘要

本項目將研究圖的圓環染色和分數染色。圖的圓環染色和分數染色均是圖的經典染色的自然推廣。其研究受到廣泛的關注。本項目關注的幾個主要問題是線圖的圓環色數的取值範圍、直積圖的圓環色數和分數色數與因子圖的圓環色數和分數色數間的關係和3-正則圖的分數色數問題。希望找出一些被線圖的圓環色數的取值範圍覆蓋的有理數的區間和一些與線圖的圓環色數的取值範圍不相交的有理數的區間。得到比較好的大圍長的3-正則圖的分數色數上界。

結題摘要

本項目著重研究圖的染色及相關問題，包括圖的圓環染色，帶符號圖的圓環流、圖的反魔方標號，圖的分數染色，圖的列表染色和線上列表染色以及圖的點邊賦權等。在圖的圓環染色方面，證明了對任意整數n， 區間[n, n+1/6]的任意有理數都是某個有限圖的線圖的圓環色數，從而否定了Ghebleh有關該問題的一個猜想。本項目比較系統地研究了帶符號圖的圓環流。將Lovasz-Thomassen-Wu-Zhang關於圖的圓環流的突破性結果推廣到帶符號圖的圓環流。關於圖的列表染色，Alon-Tarsi證明二部圖若最大平均度數為2（k-1），則該圖k-可選。我們證明存在二部圖，其圍長任意大，任意真子圖最大平均度數為2（k-1），但不是k-可選的。同時，給出了經典的Erdos定理（存在圍長和色數任意大的圖）的一個新的、簡單的證明。線上列表染色方面， 證明了線上形式的Ohba猜想對獨立數不超過3的圖成立，證明了局部平面圖5-線上可選，強化了著名的Thomasen有關局部平面圖5-可染的定理。關於圖的點邊賦權問題，刻畫了所有(2m, m)-線上可選圖，否定了Voigt關於3-可選臨界圖均為(4, 2)-可選的猜想，同時證明一個弱一些的命題成立。對於圖的點邊賦權問題做了比較多的研究，一個重要的結果是證明了所有圖都是點邊賦權(2, 3)-可選的。在圖的反魔方標號得研究方面，證明了所有度數＞1 的正則圖均有反魔方標號。為著名的反魔方標號猜想提供了有力的支持。在分數染色方面，在證明了分數形式的Hedetniemi猜想的基礎上，研究了圖的無重複分數問題，確定了圈圖和無二度點的樹圖的無重複分數色數。本項目共發表了27篇SCI論文。項目組成員獲得4項國家自然科學基金面上項目。十多次應邀在重要國際學術會議做大會報告(Plenary Speaker)和邀請報告(Invited Speaker)。