The Hochbaum–Nishizeki–Shmoys conjecture on polynomial-time edge coloring

Let $G$ be a multigraph, let $\Delta(G)$ denote its maximum degree, and let

$$\Gamma(G):=\max_{H\subseteq G}\left\lceil\frac{|E(H)|}{\left\lfloor\frac{1}{2}|V(H)|\right\rfloor}\right\rceil$$

be its density. A proper edge-coloring assigns colors to the edges so that adjacent edges receive different colors.

Hochbaum–Nishizeki–Shmoys conjecture. There exists a polynomial-time algorithm that finds a proper edge-coloring of every multigraph $G$ using $\max\\{\Delta(G)+1,\Gamma(G)\\}$ colors.

The paper states that its main theorem confirms this conjecture by providing such an algorithm. Therefore the conjecture is solved.