Edge Coloring and Edge Cover Packing

Georgia State University Research Foundation, Inc., Atlanta GA

Investigators

Abstract

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.