Graph Edge Decomposition and Graph Toughness

这个项目集中在图论中的两个中心主题：最优边缘划分为避免某些冲突的类和哈密顿循环问题。这两个问题都具有重要的理论意义，在组合优化和计算机科学等领域有着广泛的应用。一般来说，寻找某一类边的最优划分是一个np完全问题，确定图中哈密顿循环的存在性也是一个np完全问题。在这两个领域的两个著名猜想的背景下，本项目致力于开发保证给定类型的最优边划分或图中哈密顿循环存在的充分条件，并为这两个领域的研究开发新的技术。该项目还包含适合学生的研究问题。具体来说，PI将继续调查两个长期存在的猜想：1986年的Chetwynd和Hilton的Overfull猜想和1973年的Chvatal的韧性猜想。PI和她的合作者最近对这两种猜想都做出了重大贡献，但它们仍处于开放状态。对于Overfull猜想，扩展了她和她的合作者最近开发的一些技术，PI将首先研究n阶和任意接近一半n的最小度的大图，并探索算法方面。然后，她将通过应用和扩展从第一步得到的结果来攻击只有最大度约束的大图的猜想。她还将扩展技术来攻击相关的线性树性猜想。对于韧性猜想，PI将通过在给定韧性条件下寻找跨越子结构的一系列问题来获得更多的见解。这些问题包括Bauer、Broersma和Schmeichel在一项关于图形韧性的调查中提出的两个具有挑战性的问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project focuses on two central topics in graph theory: optimal edge partition into classes that avoid certain conflicts and the Hamiltonian cycle problem. Both problems have significant theoretical importance and have broad applications in fields such as combinatorial optimization and computer science. In general, finding an optimal edge partition of a certain kind is an NP-complete problem, so is determining the existence of a Hamiltonian cycle in a graph. Under the background of two famous conjectures from the two areas, this project dedicates to developing sufficient conditions that guarantee an optimal edge partition of a given type or the existence of a Hamiltonian cycle in a graph and developing novel techniques for both areas of research. The project also contains research problems that are suitable for students.Specifically, the PI will continue her investigation of two longstanding conjectures: the Overfull Conjecture of Chetwynd and Hilton from 1986 and the Toughness Conjecture of Chvatal from 1973. The PI and her collaborators have recently made significant contributions to both conjectures, but they remain open. For the Overfull Conjecture, extending some techniques that she and her collaborators developed recently, the PI will first investigate it for large graphs of order n and minimum degree arbitrarily close to half of n and explore algorithmic aspects. Then she will attack the conjecture for large graphs with only maximum degree constraints by applying and extending results obtained from the first step. She will also expand the techniques to attack the related Linear Arboricity Conjecture. For the Toughness Conjecture, the PI will gain more insights into it by working on a series of problems in finding spanning substructures under a given toughness condition. The problems include two challenging questions posed by Bauer, Broersma, and Schmeichel in a survey on graph toughness.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.