Graph minors, topological minors, and immersions

点击翻译按钮获取中文摘要

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.