关于图顶点划分的 Thomassen 猜想

本项目主要围绕 Thomassen 猜想相关的划分问题展开研究。 取得了以下重要成果。.我们证明了每一个有m条边且最小度大于等于2的图都有一个平衡划分使得两个子集各自导出一个边数不超过m/3的子图，且证明了三角形是唯一一个极图。文章发表在图论界国院顶尖期刊Journal Combinatorial Theory Ser. B。 我们将Kaneko的结果推广到不含相邻三角形的图类上，将Diwan结果推广到不含三角形且任一个顶点至多含于一个4-圈的图类上。在划分的算法方面， 我们利用半定规划方法结合随机ROUNDING 技巧，设计了新的算法，与前人的算法相比较，数据实验结果有很大改进。文章发表在 Sciences China Mathematics上。我们还在在禁用导出子图条件下图的染色数与团数的关系方面取得了重要进展，文章发表在Siam Journal on Discrete Mathematics。