No label defined (Q4527280)

Let \(\Delta=\Delta(G)\) and \(q(G)\) be the maximum degree and chromatic index of a multigraph~\(G\) with \(n=n(G)\) vertices and \(m=m(G)\) edges. Clearly, \(q(G)\geq\Delta(G)\). The problem of deciding whether \(q(G)=\Delta(G)\) is known to be NP-complete. M.~K.~Goldberg (1984) conjectured that \[ q(G)=\max_{H\subseteq G} \left\lceil\frac{m(H)}{\left\lfloor\frac{n(H)}{2}\right\rfloor}\right\rceil \] whenever \(q(G)>\Delta(G)+1\). A relaxation of this conjecture for \(q(G)>\frac{11\Delta(G)+8}{10}\) was confirmed by \textit{T.~Nishizeki} and \textit{K.~Kashiwagi} [SIAM J. Discrete Math. 3, No. 3, 391-410 (1990; Zbl 0702.05036)]. In the article under review, a simple proof of this result is provided.