Edge coloring multigraphs

For a multigraph $G$, let $\chi'(G)$ denote the chromatic index of $G$, let $\Delta(G)$ be the maximum degree of $G$, and let $\Gamma(G) = \max\{\lceil 2|E(H)|/(|V (H)|-1)\rceil: H \subseteq G \mbox{ and } |V(H)| \mbox{ odd}\}$. As a generalization of Vizing’s classical coloring result for simple graphs, the Goldberg-Seymour conjecture, posed around 1973, asserts that $\chi'(G)=\max\{\Delta(G), \Gamma(G)\}$ or $\chi'(G)=\max\{\Delta(G) + 1, \Gamma(G)\}$. Hochbaum, Nishizeki, and Shmoys also conjectured in 1986 that a $\max\{\Delta(G) + 1, \chi'(G)\}$-edge-coloring of $G$ can be found in polynomial time in the size of $G$. We give a proof of the Goldberg-Seymour conjecture, which also confirms the Hochbaum-Nishizeki-Shmoys conjecture by finding a $\max {\Delta(G) + 1, Gamma(G)\}$-edge-coloring of $G$ in polynomial time. Joint work with G. Chen, Y. Hao, and W. Zang.