关于图顶点划分的 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。