Graph Decompositions and Their Applications

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

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.