{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:42:57Z","timestamp":1753893777872,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.37236\/11049","type":"journal-article","created":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T01:21:56Z","timestamp":1666056116000},"source":"Crossref","is-referenced-by-count":0,"title":["Vizing's and Shannon's Theorems for Defective Edge Colouring"],"prefix":"10.37236","volume":"29","author":[{"given":"Pierre","family":"Aboulker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guillaume","family":"Aubian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chien-Chung","family":"Huang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2022,10,7]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i4p1\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v29i4p1\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T01:21:57Z","timestamp":1666056117000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v29i4p1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,7]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,10,6]]}},"URL":"https:\/\/doi.org\/10.37236\/11049","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2022,10,7]]},"article-number":"P4.1"}}