Graph minors, topological minors, and immersions

图次要项、拓扑次要项和浸入式

• 批准号: 1929851
• 负责人: Chun-Hung Liu
• 金额: $ 8.18万
• 依托单位: Texas A&M University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-08-16 至 2021-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1929851&HistoricalAwards=false
• 关键词: Graph; minors; topological; 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.

组合学中的一个中心区域是对没有某些子结构的图形性质的研究。该项目针对三个密切相关的图形遏制关系解决了子结构：未成年人，拓扑未成年人和沉浸式。自70年前以来，已经提出了与这些遏制关系有关的问题。近几十年来，有关图形未成年人的成功取得了巨大的成功，并导致了与组合学以外的学科有关的许多应用，例如理论计算机科学，电气工程和生物学。但是，关于图形未成年人的一些问题及其在拓扑未成年人和浸入方面的加强或变化仍未解决。该项目解决了该领域的主要猜想。积极的解决方案将导致理论计算机科学和优化中的立即应用。根据早期有关图形未成年人的富有成果的应用，预计会有更多的潜在应用。该项目包括许多适合研究生和高级本科生的研究问题。该项目中涉及的主题包括图形着色，Erdos-Posa属性，良好的秩序和一般的结构性特性。该项目的一个目的是解决或至少在有关Hadwiger在着色图上的变化或放松的一组问题上取得了重大进展，而没有大集团小数，拓扑次要的或浸入式。另一个目的是证明拓扑未成年人的最大半整合包装与击球组的最小尺寸之间的关系，这是对托马斯在半综合包装未成年人中的猜想的加强。此外，将考虑纳什·威廉姆斯（Nash-Williams）在良好的秩序图上通过牢固的沉浸关系的猜想。攻击这些猜想的策略证明了针对这三个围护关系的固定图和利用PI早期工作中开发的固定图的新结构定理，以及用于解决有关图形未成年人的问题的文献。

项目成果

A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three

用于排除没有三阶边切割的图中的浸没的全局分解定理

• DOI: 10.1016/j.jctb.2022.01.005
• 发表时间: 2022
• 期刊: Series B
• 作者: Liu, Chun-Hung

Packing and covering immersions in 4-edge-connected graphs

在 4 边连接图中封装和覆盖浸没

• DOI: 10.1016/j.jctb.2021.06.005
• 发表时间: 2021
• 期刊: Series B
• 作者: Liu, Chun-Hung

A Unified Proof of Conjectures on Cycle Lengths in Graphs

• DOI: 10.1093/imrn/rnaa324
• 发表时间: 2019-04
• 期刊: arXiv: Combinatorics
• 作者: Jun-ming Gao;Qingyi Huo;Chun-Hung Liu;Jie Ma

Phase transition of degeneracy in minor-closed families

• DOI: 10.1016/j.aam.2023.102489
• 发表时间: 2019-12
• 期刊: Adv. Appl. Math.
• 作者: Chun-Hung Liu;F. Wei

Clustered variants of Hajós' conjecture

Hajós 猜想的聚类变体

• DOI: 10.1016/j.jctb.2021.09.002
• 发表时间: 2022
• 期刊: Series B
• 作者: Liu, Chun-Hung;Wood, David R.
• 通讯作者: Wood, David R.