A short proof of the Goldberg-Seymour conjecture

For a multigraph G, χ'(G) denotes the chromatic index of G, Δ(G) the maximum degree of G, and Γ(G) = max\ 2|E(H)|/|V(H)|-1 : H ⊆ G and |V(H)| odd\. As a generalization of Vizing's classical coloring result for simple graphs, the Goldberg-Seymour conjecture, posed in the 1970s, states that χ'(G)=max\Δ(G), Γ(G)\ or χ'(G)=max\Δ(G) + 1, Γ(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|⁵|E|³) time algorithm for finding a max\Δ(G) + 1, Γ(G)\-edge-coloring of G.