Density and Edge Coloring

图形是一种数学结构，可用于对对象之间的关系进行建模。以社交网络为例：网络中的每个人都可以被认为是一个点，称为顶点，如果两个人是朋友，他们就被一条边连接在一起。边着色研究的是在一定的限制条件下对图的边进行着色的方法。例如，正确的边着色是将颜色分配给图的边，以使共享相同顶点的两条边没有相同的颜色。一个重要的问题是找到可以用于适当的边着色的尽可能少的颜色。在这个项目中，PI计划解决边着色中的公开问题，以及推导出图着色问题的有效算法。边着色的理论结果和算法在网络问题、通信问题、调度问题等许多优化问题中都有重要的应用。密度作为图的一个参数，涉及到边着色中的许多公开问题。这个项目的主要目标是应用密度相关的技术，例如在攻击Goldberg-Seymour猜想时得到的Tashkinov树方法的推广，以及在探索Hilton-赵猜想时发展的广义Kempe变换方法，以解决下列与密度有关的问题：(1)Hilton-赵猜想和过满的猜想；(2)Gupta的共密度猜想；(3)Goldberg对多重图的全着色猜想的推广；以及(4)找到在上述猜想中具有最佳颜色数目的着色图的有效算法。PI还希望通过探索上述问题来开发与密度相关的新技术。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.