Density and Edge Coloring

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

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.