Edge Coloring and Edge Cover Packing

图论是对图的研究，图是用于对对象之间的成对关系进行建模的数学结构。图是由边相连的顶点组成的。图的边着色问题是图论领域中一个久负盛名的课题。这是一个基本的组合优化问题：用尽可能少的颜色给图的边着色，使每条边接收一种颜色，而相邻的边，即与公共顶点关联的不同边，接收不同的颜色。它有丰富的理论、丰富的应用和许多美好的猜想。它不仅被数学家研究，也被计算机科学家研究。在这个项目中，PI将开发新的重新着色技术来破解该领域的基本猜想。该项目将同时培训研究生并将研究成果传播给该领域的研究人员。该项目的主要主题是Tashkinov树方法的扩展和变化，Tashkinov树方法是迄今为止发展起来的最强大和最复杂的多重图边着色技术。以前，几乎所有的边着色技术都是基于Viing的邻接引理的，这有一定的局限性。Tashkinov树方法推广了多图的扇图和Kierstead路的早期方法。围绕Tashkinov树的发展为研究图的边着色开辟了新的途径，并导致了许多重要的新结果，例如证明了著名的Goldberg-Seymour猜想。研究人员目前正在开发针对简单图的更强版本的塔什基诺夫树型结果，这将导致该领域一些长期猜测的实质性进展。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph is made up of vertices which are connected by edges. Graph edge-coloring is a well-established subject in the field of graph theory. It is a basic combinatorial optimization problem: color the edges of a graph with as few colors as possible such that each edge receives a color and adjacent edges, that is, different edges incident to a common vertex, receive different colors. It has a rich theory, abundant applications, and many beautiful conjectures. It is studied not only by mathematicians but also by computer scientists. In this project, the PI will develop new re-coloring techniques to attack fundamental conjectures in the field. The project will, at the same time, train graduate students and disseminate results to researchers in the area.The main topic of this project concerns extensions and variations of the method of Tashkinov trees, which is the most powerful and sophisticated technique for multigraph edge-coloring developed so far. Previously, almost all edge-coloring techniques were based on Vizing's adjacency lemmas, which have certain limitations. The Tashkinov tree method generalizes the earlier methods of Vizing fans and Kierstead paths for multigraphs. Developments around Tashkinov trees have opened new avenues in the study of graph edge-coloring and led to a number of significant new results such as the proof of the well-known Goldberg-Seymour Conjecture. The investigator is currently developing stronger versions of Tashkinov tree type results for simple graphs, which will lead to substantial progress toward some longstanding conjectures in this field.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.