Graph Decompositions and Their Applications

图分解及其应用

• 批准号: 1954054
• 负责人: Chun-Hung Liu
• 金额: $ 15万
• 依托单位: Texas A&M University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2020
• 资助国家: 美国
• 起止时间: 2020-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1954054&HistoricalAwards=false
• 关键词: Graph; Decompositions; Their; Applications

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.

图理论是组合学的核心研究方向。图是抽象的数学对象，已广泛用于建模不同主题中的问题，例如网络理论，集成电路设计和调度理论。在复杂图上解决问题的一种一般方法是首先将原始图分解为更易于处理的零件，解决这些问题上的问题，最后从答案中为这些较小的零件的答案构造了原始图的答案。不同的问题需要不同的分解技术，并且已经开发出许多分解定理并成功地应用了长期立式合同。但是，尚不清楚那些开发的分解定理是否足以解决其他开放问题。该项目的目的是通过开发新的结构分解定理来丰富工具包，应用它们和其他开发的定理来解决图理论和理论计算机科学中的主要猜想，以解决这个基本问题。该项目包括许多适合研究生和高级本科生的研究问题。该项目取得的进展将提高数学知识并为教育做出贡献。该项目的目的是证明新的分解定理并将其应用于图理论和计算机科学中的开放问题。一个目的是证明浸入式家族中图形的全球树状分解定理，并将其应用于与Abu-Khzam，Langston，Langston，Lescure和Meyniel在图形上的猜想有关的开放问题。此外，将考虑最近针对分层树分类的新概念，以便将算法的算法结果概括为少量封闭的家族到严格的宽类图，例如嵌入固定表面中的图形，并允许一些交叉。该项目的另一个目的是在岛屿分解上解决Dvorak和Norin的猜想，这是由于加强Hadwiger在次要家庭中着色图的放松而促进的。攻击上述问题的策略是进一步研究图形的结构，其中将涉及新的想法，并且将探讨PI的早期结果和文献中的其他结构定理。该奖项反映了NSF的法定任务，并被视为值得通过基金会的知识分子优点和更广泛影响的评估审查审查标准来通过评估来获得支持。

项目成果

Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth

正确的无冲突列表着色、奇数次要、细分和分层树宽

• DOI: 10.1016/j.disc.2023.113668
• 发表时间: 2024
• 期刊: Discrete Mathematics
• 影响因子: 0.8
• 作者: Liu, Chun-Hung

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

Defective Coloring is Perfect for Minors

有缺陷的色彩非常适合未成年人

• DOI: 10.1007/s00493-024-00081-8
• 发表时间: 2024
• 期刊: Combinatorica
• 影响因子: 1.1
• 作者: Liu, Chun-Hung

Legacy of Robin Thomas

罗宾·托马斯的遗产

• DOI: 10.1090/noti2497
• 发表时间: 2022
• 期刊: Notices of the American Mathematical Society
• 作者: Liu, Chun-Hung