Graph minors, topological minors, and immersions

组合学的一个中心领域是研究没有特定子结构的图的性质。该项目涉及三个密切相关的图包含关系的子结构：未成年人，拓扑未成年人和浸入。有关这些遏制关系的问题早在70多年前就已提出。近几十年来，关于图的未成年人取得了巨大的成功，并导致了许多应用到学科以外的组合，如理论计算机科学，电气工程和生物学。然而，关于图的子式以及它们在拓扑子式和浸入方面的加强或变化的一些问题仍然没有解决。该项目涉及这一领域的主要问题。正解将直接应用于理论计算机科学和优化。基于对图子式的早期研究成果的丰富应用，预计会有更多潜在的应用。本项目包含了大量适合研究生和高年级本科生的研究课题，涉及的主题包括图的着色、Erdos-Posa性质、良拟序和一般结构性质。这个项目的一个目标是解决或至少取得重大进展的一组问题的变化或放宽Hadwiger猜想着色图没有大团子，拓扑子或浸入。另一个目的是证明拓扑子式的半整packing的最大尺寸与碰集的最小尺寸之间的关系，这是对托马斯关于半整packing子式猜想的加强.此外，我们还利用强浸入关系考虑了Nash-Williams关于良拟序图的猜想。攻击这些结构的策略是证明新的结构定理，排除一个固定的图与这三个包含关系和利用工具，在PI的早期工作和文献中开发的解决问题的图未成年人。

A central area in combinatorics is the study of properties of graphs without certain substructures. This project addresses substructures with respect to three closely related graph containment relations: minors, topological minors, and immersions. Problems related to these containment relations have been proposed since more than 70 years ago. Great successes about graph minors were obtained during recent decades and led to numerous applications to disciplines other than combinatorics, such as theoretical computer science, electrical engineering and biology. However, several problems about graph minors and their strengthening or variations with respect to topological minors and immersions remain unsolved. This project addresses major conjectures in this area. Positive solutions will lead to immediate applications in theoretical computer science and optimization. More potential applications are expected based on fruitful applications of earlier work about graph minors. This project includes plenty of research problems that are suitable for graduate students and advanced undergraduate students.Topics addressed in this project including graph coloring, Erdos-Posa property, well-quasi-ordering and general structural properties. One objective of this project is to solve or at least make significant progress on a group of questions about variations or relaxations of Hadwiger's conjecture on coloring graphs with no large clique minor, topological minor or immersion. Another objective is to prove a relationship between the maximum size of half-integral packing of topological minors and the minimum size of hitting sets, which is a strengthening of Thomas' conjecture on half-integral packing minors. Furthermore, Nash-Williams' conjecture on well-quasi-ordering graphs by the strong immersion relation will be considered. The strategies for attacking these conjectures are proving new structure theorems for excluding a fixed graph with respect to these three containment relations and exploiting tools that were developed in the PI's earlier work and in the literature for solving problems about graph minors.