Connectivity and Minors in Graph Theory

连通性是图论中最基本的特征之一， 图表。几乎所有的图论问题，包括各种 着色问题，路由问题和嵌入问题是非常重要的。 与连通性密切相关。然而，连通性不是 在大多数图形操作下都保留了这些操作，这些操作通常需要在 学习图表。因此，知道如何执行这些操作， 特别是，小操作，同时保持连通性， 一个非常重要和基本的问题， 今天在本项目中，PI建议调查三个（集 图的连通性问题。而不是专注于 局部属性，如可收缩边缘的存在，这些 问题更多地关注k-连通的全局结构 图表。PI的第一个问题是Ramsey型问题， 基本上说，一个大的完全二分图子式是 不可避免地从每一个高度连接的大型图。问题二是 解决未成年人的连接问题它寻求最佳功能 f（k，m），若G是k连通图H的子图，则H 有一个k-连通子式H'，其中至多f（k，|E（G）|）边缘，使得 H'也包含G作为小调。这个项目的第三个问题是 这是一个猜想，它断言西摩的图形版本 分裂定理可以从3连通图推广到 所有这些提出的问题都是重要的和基本的。他们的 解决方案将提供强大的新工具， 连通性，这将影响图论的许多领域。为 例如，这些解决方案可能会对以下问题产生重大影响， 无K（6）-子式图和无Petersen-子式图的刻划 图，图论中两个著名的开放问题。而且这 研究也是非常重要的观点， 应用.它可以为改善网络带来新的见解 可靠性和网络安全性。

Connectivity and Minors in Graph TheoryAbstractConnectivity is one of the most fundamental characteristics of graphs. Almost all problems in graph theory, including various coloring problems, routing problems, and embedding problems are very closely related to connectivity. However, connectivity is not preserved under most graph operations which are usually needed in studying graphs. Thus, knowing how to perform these operations, in particular, minor operations, while maintaining the connectivity is a very important and fundamental problem facing graph theorists today. In this project, the PI proposes to investigate three (sets of) problems on graph connectivity. Instead of concentrating on local properties like the existence of contractible edges, these problems are more concerned with global structure of k-connected graphs. The PI's first problem is a Ramsey-type problem which basically says that a large complete-bipartite-graph-minor is unavoidable from every highly connected large graph. Problem two is about fixing the connectivity of a minor. It seeks the best function f(k,m) for which, if G is a minor of a k-connected graph H, then H has a k-connected minor H' with at most f(k,|E(G)|) edges such that H' also contains G as a minor. The third problem in this project is a conjecture which asserts that the graph version of Seymour's splitter theorem can be extended from 3-connected graphs to k-connected graphs for all k.All these proposed problems are important and fundamental. Their solutions will provide powerful new tools for dealing with high connectivity, and that will affect many areas of graph theory. For instance, these solutions could have a big impact on problems like characterizing K(6)-minor-free graphs and Petersen-minor-free graphs, two well-known open problems in graph theory. Moreover, this study is also very important from the point of view of applications. It could bring new insights on improving network reliability and network security.