Graph Edge Coloring

边着色问题（ECP）的目标是用最少的颜色给图的边着色，使得没有两个相邻的边接收相同的颜色。它的最佳值称为色指数。除了其巨大的理论兴趣，ECP出现在各种应用，如调度问题和光纤通信。 它吸引了许多领域的研究，如图论，组合优化和理论计算机科学。Holyer在1981年证明了确定色指数一般是NP-完全的，因此除非NP= P，否则没有有效的算法来精确求解ECP。因此，广泛的研究一直集中在近最优解，色指数的良好估计，以及ECP可以在多项式时间内精确求解的一些条件。 Goldberg-Seymour猜想，最近被PI和他的合作者证实，意味着我们可以在多项式时间内近似色指数的真实值之一。PI和他的研究生们一直致力于确定多项式时间内色指数可达的图族，色指数的一个值得注意的下界是最大度.这两个不变量之间的关系被很好地研究，有许多美丽的结果。 除了最大度之外，色指数还有另一个下界，称为密度。关于密度在决定色指数时所起的作用，一些长期存在的理论已经被提出，然而，这些理论大多缺乏技术上的突破。 这两个下界的组合给出了所有（多）图的分类：如果图的色指数等于这两个下界的最大值，则图是第一类，否则是第二类。显然，第一类图是那些色指数可以多项式时间计算的图，并且所有第一类简单图都是第一类图。这个项目的目的是显示几个常见的家庭属于第一类图。在这个方向上有三个长期未解决的问题（最初以不同的术语陈述）：具有大最大度的简单图是第一类的（希尔顿的过满猜想）;所有平面图都是第一类的（西摩的精确猜想）;从正则简单图通过加倍每条边得到的图是第一类的（广义富克尔森猜想）。 PI和他的合作者最近开发的方法已经显示出对这些问题取得更实质性进展的潜力。此外，PI计划扩展边着色技术，以解决图全着色中的一些问题，包括Goldberg关于全色数和色指数相等的猜想。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The edge-coloring problem (ECP) aims to color the edges of a graph with the minimum number of colors so that no two adjacent edges receive the same color. Its optimal value is called the chromatic index. In addition to its great theoretical interest, ECP arises in various applications such as the scheduling problem and fiber-optic communication. It has attracted tremendous research efforts in several fields, such as graph theory, combinatorial optimization, and theoretical computer science. Holyer in 1981 proved that it is NP-complete in general to determine the chromatic index, so there is no efficient algorithm for solving the ECP exactly unless NP=P. Hence, extensive research has been focusing on near-optimal solutions, good estimates of the chromatic index, and some conditions under which the ECP can be precisely solved in polynomial-time. The Goldberg-Seymour conjecture, confirmed recently by the PI and his collaborators, implies that we can approximate the chromatic index within one of its true value in polynomial time. The proposed research lies in determining the families of graphs whose chromatic index can be found in polynomial-time, which the PI has been and will continue working on with his current and former graduate students.A noticeable lower bound for the chromatic index is the maximum degree. The relationship between these two invariants is well studied, with many beautiful results. Apart from the maximum degree, there is another lower bound for the chromatic index, called density. Some longstanding conjectures have been brought forward on the roles that density plays when determining the chromatic index, however, most of which lack techniques to attack. The combination of these two lower bounds gives a classification of all (multi)graphs: a graph is of the first class if its chromatic index equals the maximum value of these two lower bounds and is of the second class otherwise. Clearly, the first class graphs are those whose chromatic index can be computed polynomial-time, and all class one simple graphs are of the first class. This project aims to show several commonly known families of graphs belonging to the first class. There are three longstanding unsolved problems in this direction (stated initially in different terms): simple graphs with a large maximum degree are of the first class (Hilton’s Overfull Conjecture); all planar graphs are of the first class (Seymour’s Exact Conjecture); the graph obtained from a regular simple graph by doubling each edge is of the first class (The Generalized Fulkerson Conjecture). The methods developed by the PI and his collaborators recently have shown some potential for more substantial progress toward these problems. Additionally, the PI plans to extend the techniques developed for edge-coloring to tackle some problems in graph total-coloring, including Goldberg’s conjecture on the equality of the total chromatic number and the chromatic index.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.