Connectivity and Minors in Graph Theory

图论中的连通性和次要性摘要连通性是图最基本的特征之一。图论中的几乎所有问题，包括各种着色问题、路由问题和嵌入问题，都与连通性密切相关。然而，在研究图的过程中，大多数图运算都不能保证图的连通性。因此，了解如何执行这些操作，特别是小操作，同时保持连通性是当今图论理论家面临的一个非常重要和基本的问题。在这个项目中，PI建议研究图连通性的三个（一组）问题。这些问题不是集中于局部性质，如可收缩边的存在性，而是更关注k连通图的全局结构。PI的第一个问题是ramsey型问题，它基本上是说每个高度连通的大图中都不可避免地会出现一个大的完全二部分图。问题二是关于修复未成年人的连通性。它寻找最优函数f(k,m)，如果G是k连通图H的次边，那么H有一个k连通的次边H‘，最多有f（k, b| E(G)|）条边使得H’也包含G作为次边。本课题的第三个问题是一个猜想，该猜想断言Seymour的分裂定理的图版本可以从3连通图推广到k连通图，对于所有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.