《關於圖頂點劃分的 Thomassen 猜想》是依託南京師範大學，由許寶剛擔任項目負責人的面上項目。
基本介紹
- 中文名：關於圖頂點劃分的 Thomassen 猜想
- 項目類別：面上項目
- 項目負責人：許寶剛
- 依託單位：南京師範大學
項目摘要,結題摘要,
項目摘要
圖的頂點劃分問題一直是圖論研究的重點，很多圖論問題都可以表述為某種特殊的劃分問題，比如圖的經典染色問題就是要求將圖的頂點劃分成儘量少的獨立集，而最大二部子圖問題就是要求將圖的頂點劃分成兩個子集使它們相互之間的邊最多。1983年，丹麥科學院院士、著名圖論學家 Thomassen 提出一個猜想： 對任意給定的正整數 r，存在一個整數 k=k(r)，使得對每一個k-連通圖 G 及 V（G）的任一個含至多 r 個點的子集 X， 存在 V（G）的一個劃分 S和T滿足X包含於 S， G[S] 和 G[T] 都是 r-連通的且S中的每一個點在 T 中至少有 r 個鄰點。 這一猜想的實質性進展將對研究圖的子圖結構、連通性等提供非常重要的工具,有非常重要的理論意義。本項目擬圍繞 Thomassen 猜想展開研究，爭取在這方面取得一些進展。
結題摘要
本項目主要圍繞 Thomassen 猜想相關的劃分問題展開研究。 取得了以下重要成果。 我們證明了每一個有m條邊且最小度大於等於2的圖都有一個平衡劃分使得兩個子集各自導出一個邊數不超過m/3的子圖，且證明了三角形是唯一一個極圖。文章發表在圖論界國院頂尖期刊Journal Combinatorial Theory Ser. B。 我們將Kaneko的結果推廣到不含相鄰三角形的圖類上，將Diwan結果推廣到不含三角形且任一個頂點至多含於一個4-圈的圖類上。在劃分的算法方面， 我們利用半定規劃方法結合隨機ROUNDING 技巧，設計了新的算法，與前人的算法相比較，數據實驗結果有很大改進。文章發表在 Sciences China Mathematics上。我們還在在禁用導出子圖條件下圖的染色數與團數的關係方面取得了重要進展，文章發表在Siam Journal on Discrete Mathematics。
