Connectivity 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.
