The Goldberg-Seymour conjecture on the edge-coloring of multigraphs

The Goldberg-Seymour conjecture on the edge-coloring of multigraphs

-
Guangming Jing, Georgia State University
Fine Hall 224

Given a multigraph G=(V,E), the ``edge-coloring problem'' (ECP) is to color the edges of G with the minimum number of colors such that no two incident edges receive the same color. This problem can naturally be formulated as an integer program, and its linear programming relaxation is called the ``fractional edge-coloring problem'' (FECP). The optimal value of ECP (resp. FECP) is called the ``chromatic index'' (resp. ``fractional chromatic index'') of G, and is denoted by chi'(G) (resp. chi^*(G)). Let D(G) be the maximum degree of G, let  w(G) be the maximum of 2|E(H)|/(|V(H)|-1) over all subgraphs H of G with |V(H)| odd and at least three, and let W(G) be the smallest integer at least w(G).  Clearly, max (Delta(G), W(G)) is a lower bound for chi'(G).  As shown by Seymour, chi^*(G)=max(D(G), W(G))$. 

In the 1970s Goldberg and Seymour independently conjectured that chi'(G) leq max (D(G)+1, W(G)), which if true implies that, first, every multigraph G satisfies chi'(G)-chi^*(G) leq 1, so FECP enjoys a fascinating integer rounding property; second, ECP can be approximated within one of the optimum, and hence is one of the ``easiest" NP-hard problems; third, there are only two possible values for chi'(G), so an analogue of Vizing's theorem on edge-colorings of simple graphs holds for multigraphs. In this talk, we will discuss a proof of this conjecture. This is joint work with Guantao Chen and Wenan Zang.