Graph Edge Coloring

Georgia State University Research Foundation, Inc., Atlanta GA

Investigators

Abstract

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.