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

Pierre Aboulker ; Guillaume Aubian ; Chien-Chung Huang

The electronic journal of combinatorics, Tome 29 (2022) no. 4

Résumé

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}(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'_{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'_d(G)$. These results generalize classic results on the chromatic index of a graph by Shannon, Holyer, Leven and Galil and extend a result of Amini, Esperet and van den Heuvel.

Détail

DOI : 10.37236/11049

Classification : 05C15, 05C70
Mots-clés : \((k, d)\)-edge colourable multigraph, Vizing's theorem