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

Abstract

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^{\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 $\Delta$ is $(\lceil \frac{\Delta }{d}\rceil ,d)$-edge colourable if $d$ is even and $(\lceil \frac{3\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^{\prime }(G)\in \{\lceil \frac{\Delta }{d}\rceil ,\lceil \frac{\Delta +1}{d}\rceil \}$ and characterize the values of $d$ and $\Delta$ for which it is NP-complete to compute ${\chi }_d^{\prime }(G)$. These results generalize several classic results on the chromatic index of a graph by Shannon, Vizing, Holyer, Leven and Galil.