k-连通图子式的相关问题研究

The study on graph minor is one of graph theory topics which are considered to be so theoretical and have deepest impact. Its results and techniques will influence the development of graph theory for many years to come. The minors of k-connected graph has a close relation with the famous Hadwiger Conjecture. So it may be give a way to deal with the Hadwiger Conjecture if we can determine the minors of k-connected graph. The Hadwiger Conjecture is known to be equitvalent to the famous Four Colour Theorem for the case k=5. Further, it is found that the minimal counterexamples of Hadwiger Conjecture is 5-connected for the case k=5. Therefore the study on the minor of 5-connected graph is of great significance.. In this project, base on the Conjecture about the topological minor of 5-connected graphs which was posted by P.Seymour and the Conjecture about the minors of 5-connected graphs which was posted by G.Fijvaz, we will study the topological minors and the minors of 5-connected graphs. We will tranfer these problems to determine the structure of 5-connected graph which was imposed some detailed conditions. By the theory of fragment which is the most important tool in the graph connnectivity theory and by some techniques that we were developted in the study of 5-connected graphs, we try to deal with these two conjectures. During the course, we will develop further some tools for the study of graph minor and offer some new methods to deal with the Hadwiger Conjecture with some lower value of k..

图子式研究是图论中理论性强、所得到的成果影响深刻的研究方向之一。在其研究过程中所建立的理论和所创造的方法深刻地影响着图论的发展。连通图中的子式问题与Hadwiger猜想有密切关系，对k-连通图的子式进行有意义的刻划将对Hadwiger猜想的解答有深远的影响。 研究发现k=5时Hadwiger猜想等价于四色定理且此时Hadwiger猜想的极小反例是5-连通图，因此研究5-连通图的子式是十分有意义的工作。本项目主要围绕P.Seymour 提出的关于5-连通图拓扑子式的猜想以及G.Fijvaz提出的关于5-连通图子式的猜想，对5-连通图的拓扑子式和子式开展研究。将图子式问题转化为一些附加了具体条件的结构问题，利用研究图连通性的重要工具-断片理论以及我们所创立的5-连通图的研究技巧，尝试去解决这两个问题。在此过程中进一步探索图子式研究方法，为解决k较小时的Hadwiger 猜想提供可借鉴的方法。

图子式研究是图论中理论性强、所得到的成果影响深刻的研究方向之一。在其研究过程中所建立的理论和所创造的方法深刻地影响着图论的发展。本项目最初是想围绕P.Seymour 提出的关于5-连通图拓扑子式的猜想对5-连通图的子式开展研究。但是由于郁星星教授在2016年宣布他们证明了P.Seymour 猜想，所以我们对研究内容作了一定的修改，对图的可收边的分布， 图的约简方法，图的子式进行了研究。我们的主要结果有：.对具有可收缩边4-连通图的最小子式进行了完全刻画，证明了其中的平面图可以由C_6^2 通过一系列顶点剖分和加边得到，非平面图可以由C_5^2=K_5一系列顶点剖分和加边得到。这是一个具有本质特性而又具有广泛应用的结论。它完全解决了4-连通图的构造问题， 这是自1982年M.Martimov定理证明以来的重大进展。.其次，我们对internally 4-连通图的约简问题进行了研究，给出了10种约简运算，并构造例子说明了其中的8种是必不可少的。基本解决了internally 4-连通图的约简问题。.再次，我们证明了最小度为9的收缩临界8-连通图一定是由收缩临界4-连通图通过2-顶点分裂运算得到。在此基础上我们完全决定了子式极小且最小度为9的收缩临界8-连通图。我们的结论完全刻画了这类图的结构。.最后，我们对包含有由不可收缩边构成的生成树的3-连通的结构（称之为fox）进行刻画，证明了这类图中的每个3度点只关联一条不可收缩边。由此我们证明了在边极小的情况下这样的生成树是唯一存在的。进一步我们证明了3-连通图任意的深度优先搜索算法生成树一定有两条可收缩边，并举例说明我们的结果是最好可能的。