关于图顶点划分的 Thomassen 猜想

项目名称： 关于图顶点划分的 Thomassen 猜想

项目编号： No.11171160

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 数理科学和化学

项目作者： 许宝刚

作者单位： 南京师范大学

项目金额： 38万元

中文摘要： 图的顶点划分问题一直是图论研究的重点，很多图论问题都可以表述为某种特殊的划分问题，比如图的经典染色问题就是要求将图的顶点划分成尽量少的独立集，而最大二部子图问题就是要求将图的顶点划分成两个子集使它们相互之间的边最多。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 猜想；连通度；

英文摘要：

英文关键词： graph；vertex partition；Thomassen's Conjecture；connectivity；