Vizing's and Shannon's Theorems for defective edge colouring

We call a multigraph $(k,d)$-edge colourable if its edge set can be partitioned into $k$ subgraphs of maximum degree at most $d$ and denote as ${\chi }_d^{\mathrm{\prime }}(G)$ the minimum $k$ such that $G$ is $(k,d)$-edge colourable. We prove that for every integer $d$, every multigraph $G$ with maximum degree $\mathrm{\Delta }$ is $(\lceil \frac{\mathrm{\Delta }}{d}\rceil ,d)$-edge colourable if $d$ is even and $(\lceil \frac{3\mathrm{\Delta }-1}{3d-1}\rceil ,d)$-edge colourable if $d$ is odd and these bounds are tight. We also prove that for every simple graph $G$, $\chi’_{d}(G) \in { \lceil \frac{\Delta}{d} \rceil, \lceil \frac{\Delta+1}{d} \rceil }$andcharacterizethevaluesof$d$and$\Delta$forwhichitisNP-completetocompute$\chi’_d(G)$. These results generalize several classic results on the chromatic index of a graph by Shannon, Vizing, Holyer, Leven and Galil.