Graph Decompositions and Their Applications

图论是组合学的一个中心研究方向。图是抽象的数学对象，已被广泛用于不同学科的问题建模，如网络理论、集成电路设计和调度理论。解决复杂图上问题的一般方法是首先将原始图分解成更容易处理的块，然后解决这些块上的问题，最后根据这些小块的答案来构造原始图的答案。不同的问题需要不同的分解技术，许多分解定理已经被发展并成功地应用于解决长期存在的猜想。然而，目前尚不清楚这些发展的分解定理是否足以解决其他未决问题。这个项目的目的是通过发展新的结构分解定理来丰富工具包，并应用它们和其他发展的定理来解决图论和理论计算机科学中的主要猜想，从而解决这一基本问题。该项目包含了许多适合研究生和高级本科生的研究问题。这个项目的进展将促进数学知识的发展，并为教育做出贡献。这个项目的目的是证明新的分解定理，并将它们应用于解决图论和计算机科学中的公开问题。证明了浸没闭族中图的一个整体树形分解定理，并将其应用于解决与Abu-Khzam、Langston、Lescure和Meyniel关于图着色的猜想有关的一个公开问题。此外，将考虑最近发展的分层树分解的概念，以便将次闭族的算法结果推广到严格更广泛的图类，例如嵌入到固定曲面中的允许某些交叉点的图。这个项目的另一个目的是解决Dvorak和Norin关于岛屿分解的一个猜想，这个猜想是由Hadwiger关于次闭族着色图的猜想的一个加强而引起的。解决上述问题的策略是进一步调查图表的结构，其中将涉及新的想法，并将利用PI的早期结果和文献中的其他结构定理。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Graph theory is a central research direction in combinatorics. Graphs are abstract mathematical objects that have been extensively used to model problems in different subjects, such as in network theory, integrated circuit design, and scheduling theory. A general approach for solving problems on complicated graphs is to first decompose the original graph into more tractable pieces, solve the problems on those pieces, and finally construct the answer for the original graph from the answers for those smaller pieces. Different problems require different decomposition techniques and many decomposition theorems have been developed and successfully applied to solve long standing conjectures. However, it is unclear whether those developed decomposition theorems are sufficient to solve other open problems. The purpose of this project is to address this fundamental issue by developing new structure decomposition theorems to enrich the toolkit and applying them and other developed theorems to solve major conjectures in graph theory and theoretical computer science. This project includes many research problems that are suitable for graduate students and advanced undergraduate students. Progress made on this project will advance knowledge in mathematics and contribute to education.The aim of this project is to prove new decomposition theorems and apply them to solve open problems in graph theory and computer science. An objective is to prove a global tree-like decomposition theorem for graphs in immersion-closed families and apply it to solve an open problem related to a conjecture of Abu-Khzam, Langston, Lescure and Meyniel on graph coloring. In addition, a recent newly developed notion for layered tree-decomposition will be considered in order to generalize algorithmic results on minor-closed families to strictly wider classes of graphs, such as graphs embeddable in a fixed surface with some crossings allowed. Another objective of this project is to solve a conjecture of Dvorak and Norin on island decomposition which is motivated by a strengthening of a relaxation of Hadwiger’s conjecture on coloring graphs in minor-closed families. The strategy for attacking the above problems is to further investigate the structure of graphs, where new ideas will be involved, and the PI's earlier results and other structure theorems in the literature will be exploited.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.