Density and Edge Coloring

点击翻译按钮获取中文摘要

A graph is a mathematical structure that can be used to model relationships between objects. Take social networking as an example: each person in the network could be considered as a point, called a vertex, and two people are joined by an edge if they are friends. Edge-coloring studies the ways one can color edges of a graph under some restrictions. For example, a proper edge-coloring is an assignment of colors to the edges of a graph so that no two edges sharing the same vertex have the same color. One important problem is to find the smallest number of colors possible that can be used for a proper edge-coloring. In this project, the PI is planning to address open problems in edge-coloring as well as deriving efficient algorithms for graph coloring problems. Theoretical results and algorithms in edge-coloring have important applications in network problems, communication problems, scheduling problems, and many other optimization problems. Density as a graph parameter is involved in many open problems in edge-coloring. The main goal of this project is to apply density-related techniques such as a generalization of the Tashkinov tree method obtained in attacking the Goldberg-Seymour conjecture, and a generalized Kempe Change method developed in exploring the Hilton-Zhao conjecture, to attack the following density-related problems: (1) the Hilton-Zhao conjecture and the overfull conjecture; (2) Gupta’s co-density conjecture; (3) Goldberg’s generalization of the total coloring conjecture for multigraphs; and (4) finding efficient algorithms to color graphs with the optimal number of colors in the conjectures above. The PI is also hoping to develop new density-related techniques through exploring the above problems.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.