Graph Edge Coloring

图形边缘着色

• 批准号: 2154331
• 负责人: Guantao Chen
• 金额: $ 17.99万
• 依托单位: Georgia State University Research Foundation, Inc.
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-08-15 至 2025-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2154331&HistoricalAwards=false
• 关键词: Graph; Edge; Coloring

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.

边着色问题(ECP)的目标是用最少的颜色给图的边着色，使相邻两条边的颜色不同。它的最佳值称为色度指数。除了它的巨大理论兴趣，ECP还出现在各种应用中，如调度问题和光纤通信。它在图论、组合优化和理论计算机科学等领域吸引了巨大的研究努力。Holyer在1981年证明了确定色指数一般是NP-完全的，因此没有有效的算法来精确地求解ECP，除非NP=P。因此，广泛的研究集中在次最优解、色指数的良好估计以及在某些条件下ECP可以在多项式时间内精确求解。最近被PI和他的合作者证实的Goldberg-Seymour猜想表明，我们可以在多项式时间内在真值范围内逼近色指数。这项研究的目的在于确定图的色指数可以在多项式时间内找到的图族，PI已经并将继续与他现在和以前的研究生一起工作。一个值得注意的色指数的下界是最大度。这两个不变量之间的关系得到了很好的研究，得到了许多漂亮的结果。除了最大度数外，色指数还有另一个下界，称为密度。关于密度在确定色度指数时所起的作用，已经提出了一些由来已久的猜想，然而，大多数猜想缺乏攻击的技术。这两个下界的组合给出了所有(多)图的分类：如果图的色指数等于这两个下界的最大值，则图是第一类图，否则是第二类图。显然，第一类图是那些色指数可以计算多项式时间的图，并且所有第一类简单图都是第一类图。这个项目的目的是展示属于第一类的几个常见的图族。在这个方向上有三个长期悬而未决的问题(最初用不同的术语表述)：具有大的最大度的简单图是第一类(Hilton的满猜想)；所有平面图都是第一类(Seymour的精确猜想)；从正则简单图的每条边加倍得到的图是第一类(广义Fulkerson猜想)。PI和他的合作者最近开发的方法显示了在这些问题上取得更实质性进展的一些潜力。此外，PI计划扩展为边着色开发的技术，以解决图形全着色中的一些问题，包括Goldberg关于总色数和色指数相等的猜想。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。