Vizing's and Shannon's theorems for defective edge colouring (Q2094863)

Summary: 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^\prime_d(G)\) the minimum \(k\) such that \(G\) is \((k, d)\)-edge colourable. We prove that for every odd integer \(d\), every multigraph \(G\) with maximum degree \(\Delta\) is \((\lceil \frac{3\Delta - 1}{3d - 1} \rceil, d)\)-edge colourable and this bound is attained for all values of \(\Delta\) and \(d\). An easy consequence of Vizing's Theorem is that, for every (simple) graph \(G, \chi^\prime_d(G) \in \{\lceil \frac{\Delta}{d} \rceil, \lceil \frac{\Delta+1}{d} \rceil\}\). We characterize the values of \(d\) and \(\Delta\) for which it is NP-complete to compute \(\chi^\prime_d(G)\). These results generalize classic results on the chromatic index of a graph by \textit{C. E. Shannon} [J. Math. Phys., Mass. Inst. Techn. 28, 148--151 (1949; Zbl 0032.43203)], \textit{I. Holyer} [SIAM J. Comput. 10, 718--720 (1981; Zbl 0473.68034)], \textit{D. Leven} and \textit{Z. Galil} [J. Algorithms 4, 35--44 (1983; Zbl 0509.68037)] and extend a result of \textit{O. Amini} et al. [``Frugal colouring of graphs'', Techn. Rep. RR-6178, Institut National de Recherche en Informatique et en Automatique (2007)].