A short proof of the Goldberg-Seymour conjecture

Abstract

For a multigraph $G$, ${\chi }^{\prime }(G)$ denotes the chromatic index of $G$, $\Delta (G)$ the maximum degree of $G$, and $\Gamma (G)=\max \left\{\lceil \frac{2|E(H)|}{|V(H)|-1}\rceil :H\subseteq G\text{ and }|V(H)|\text{ odd}\right\}$. As a generalization of Vizing's classical coloring result for simple graphs, the Goldberg-Seymour conjecture, posed in the 1970s, states that ${\chi }^{\prime }(G)=\max \{\Delta (G),\Gamma (G)\}$ or ${\chi }^{\prime }(G)=\max \{\Delta (G)+1,\Gamma (G)\}$. Hochbaum, Nishizeki, and Shmoys further conjectured in 1986 that such a coloring can be found in polynomial time. A long proof of the Goldberg-Seymour conjecture was announced in 2019 by Chen, Jing, and Zang, and one case in that proof was eliminated recently by Jing (but the proof is still long); and neither proof has been verified. In this paper, we give a proof of the Goldberg-Seymour conjecture that is significantly shorter and confirm the Hochbaum-Nishizeki-Shmoys conjecture by providing an $O(|V{|}^5|E{|}^3)$ time algorithm for finding a $\max \{\Delta (G)+1,\Gamma (G)\}$-edge-coloring of $G$.