Graph Decompositions and Their Applications

图论是组合学的一个重要研究方向。图是抽象的数学对象，已被广泛用于不同学科的建模问题，如网络理论，集成电路设计和调度理论。解决复杂图问题的一般方法是首先将原始图分解为更易处理的部分，解决这些部分上的问题，最后从这些较小部分的答案中构造原始图的答案。不同的问题需要不同的分解技术，许多分解定理已经发展并成功地应用于解决长期存在的问题。然而，目前还不清楚这些发达国家的分解定理是否足以解决其他开放的问题。这个项目的目的是通过开发新的结构分解定理来解决这个基本问题，以丰富工具包，并应用它们和其他开发的定理来解决图论和理论计算机科学中的主要问题。本课题包含了许多适合研究生和高年级本科生的研究问题。该项目的进展将促进数学知识的发展，并有助于教育。该项目的目的是证明新的分解定理，并将其应用于解决图论和计算机科学中的开放问题。本文的目的是证明浸入闭族中图的一个全局树型分解定理，并应用它解决Abu-Khzam，兰斯顿，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.