Optimal Edge Decomposition of Graphs and Hamiltonicity of Tough Expanders

This proposal centers on two core themes: the optimal decomposition of a graph's edges into matchings, and the Hamiltonicity problem in tough graphs with some “expansion” properties. The decomposition of the edges of a graph into non-conflicting groups, such as matchings, is deeply rooted in combinatorial theory and holds practical significance across various fields, including computer science, operations research, and telecommunications. Additionally, the Hamilton cycle problem, a fundamental NP-complete problem, has been extensively studied, with recent advancements highlighting the importance of concepts like expansion and quasi-randomness. The project includes several research problems well-suited for graduate student involvement. In addition, the PI has planned outreach activities centered around graph theory concepts to stimulate interest in STEM fields, particularly among middle school students. The PI's proposal delves into these two pivotal problems and extends her ongoing investigation into four longstanding conjectures: the Overfull Conjecture (Chetwynd and Hilton, 1986), the Multigraph Overfull Conjecture (Stiebitz, Scheide, Toft, and Favrholdt, 2012), the Total Coloring Conjecture (Behzad and, independently, Vizing, 1960s), and the Toughness Conjecture (Chvatal, 1973). Along with collaborators, the PI has made substantial progress on each of these conjectures and aims to develop new techniques to further advance the field. This work builds on a combination of classical edge decomposition and coloring methods, alongside probabilistic techniques, which the PI will continue to refine and extend. 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.