Structure and Coloring of Sparse Graphs

PI建议继续研究稀疏图的极值性、结构性和着色性之间的相互作用，重点研究小闭图类。图小理论是图论中一个深刻而丰富的领域，最初由Robertson和Seymour在一系列23篇论文中发展起来。它仍然是一个活跃的研究领域，具有广泛的算法应用。作为理论的一部分发展起来的一些方法已经成功地应用于实际计算中。图的小图理论的核心成果之一是Robertson和Seymour的图结构定理，它给出了不包含固定图作为小图的图的近似结构描述。PI提议继续他正在进行的长期项目，该项目是与Robin Thomas共同启动的，其目标是对该理论的许多方面进行改进。特别是，该项目的目标之一是获得连通性的界限，以保证在给定大小的图中存在某些次要和相关构型（连杆，拓扑次要等）。Luke Postle和PI最近获得了上述类型的有效界，这使得他们在Hadwiger猜想（一个长期存在的问题，大大加强了四色定理）方面取得了进展。这个猜想可能是图论中最著名的开放问题，PI建议继续改进这些工具，这些工具允许最近的进展，以寻求进一步的突破。最后，PI还建议继续研究图小理论的极值方面，并开发一套用于该领域问题的通用工具。

The PI proposes to continue his investigation of interplay between extremal, structural and coloring properties of sparse graphs, focusing on minor-closed graph classes. Graph minor theory is a deep and rich area of graph theory, initially developed by Robertson and Seymour in a series of twenty three papers. It continues to be an active area of research with extensive algorithmic applications. Some of the methods developed as part of the theory have been successfully used in practical computations. One of the central results in graph minor theory is the graph structure theorem of Robertson and Seymour, which gives an approximate structural description of graphs that do not contain a fixed graph as a minor. The PI proposes to continue his ongoing long term project, started jointly with Robin Thomas, the goal of which is a refinement of many aspects of this theory. In particular, one of the goals of the project is to obtain bounds on connectivity which guarantees existence of certain minors and related configurations (linkages, topological minors, etc.) in graphs of given size. Luke Postle and the PI recently obtained effective bounds of the type mentioned above, which allowed them to make progress towards Hadwiger's conjecture, a longstanding question, which greatly strengthens the Four Color Theorem. This conjecture is possibly the most famous open problem in graph theory, and the PI proposes to continue sharpening the tools which allowed recent progress in search for further breakthroughs. Finally, The PI also proposes to continue investigation of extremal aspects of graph minor theory and the development of a suite of generic tools for problems in this area.