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作为一个子图。这个项目中的第三个问题是一个猜想，它断言Seymour分裂定理的图版可以从3-连通图推广到k-连通图，所有这些提出的问题都是重要的和基本的。他们的解决方案将为处理高连通性提供强大的新工具，这将影响图论的许多领域。例如，这些解可能会对刻画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.