Density and Algorithms in Edge Coloring and Packing

Graphs, which can be thought of as a collection of nodes, called vertices, and connections between certain of these nodes, called edges, play an important role in the theory of networks, communication, scheduling, and optimization. Edge coloring and edge packing can be considered partitions of the edges of a graph under certain restrictions. For example, a proper edge coloring partitions the edges into sets such that no two edges in the same set share a common endpoint, while an edge cover packing partitions the edges into sets such that the edges in each set cover all the vertices.

Optimal or near-optimal solutions to these problems are important for the above mentioned applications. The PI plans to explore both the theory of edge coloring and packing, as well as to develop corresponding efficient algorithms. Graduate students will be involved in this project.

Several open problems in this field are related to the graph parameter called density. Density measures the 'densest' part of a graph, which is often the main concern when solving edge coloring and packing problems. With density-related techniques such as the generalized Tashkinov tree, developed from solving the Goldberg-Seymour conjecture, and the generalized Kempe change method, developed from solving the Core conjecture of Hilton and Zhao, the PI proposes to work on (1) the Berge-Fulkerson conjecture, (2) Gupta’s co-density conjecture, (3) Goldberg’s generalization of the total coloring conjecture for multigraphs, (4) the Overfull conjecture, and (5) finding efficient algorithms to color graphs with the optimal number of colors as stated in the aforementioned conjectures.

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.