A refinement of Vizing's theorem (Q1978167)

Vizing's theorem [\textit{V. G. Vizing}, The chromatic class of a multigraph, Cybernetics 1, 32-41 (1965; see also Zbl 0166.19601)] states for any multigraph \(M\) (without loops) with maximum vertex-degree \(\Delta(M)\) and maximum edge-multiplicity \(\mu(M)\), its chromatic index \(\chi'(M)\) satisfies the inequality \(\chi'(M)\leq\Delta(M)+ \mu(M)\). In the paper under review, Vizing's theorem is refined to the inequality \[ \chi'(M)\leq \Delta(M)+ \Biggl\lceil{\mu(M)\over \lfloor g/2\rfloor}\Biggr\rceil, \] where \(g\) is the grith of \(M\) and \(\lfloor x\rfloor\) and \(\lceil x\rceil\) are, respectively, the floor and ceiling of \(x\).