Graph Edge Decomposition and Graph Toughness

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

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.