# Vizing’s and Shannon’s Theorems for defective edge colouring

Pierre Aboulker1, Guillaume Aubian1,2, Chien-Chung Huang1.
($1$) DIENS, École normale supérieure, CNRS, PSL University, Paris, France.
($2$) Université de Paris, CNRS, IRIF, F-75006, Paris, France.
Mails<EMAIL_ADDRESS><EMAIL_ADDRESS>Chien-
<EMAIL_ADDRESS>
###### 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^{\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 that this bound is attained for all values of $\Delta$ and $d$.
An easy consequence of Vizing Theorem is that
$\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 Shannon, Holyer, Leven and Galil and extend
a result of Amini, Esperet and ven den Heuvel.

##  1 Introduction

_Graphs_ in this paper are finite, undirected, and without loops, but may have
multiple edges. A graph is simple if it has no multiple edge. Let $G$ be a
graph. We denote by $\Delta(G)$ the maximum degree of $G$. An _edge colouring
of $G$ with defect $d$_ is a colouring of its edge set in such a way that each
vertex is incident with at most $d$ edges of the same colour. We say that $G$
is _$k$ -edge colourable with defect $d$_, or simply _$(k,d)$ -edge
colourable_ if $G$ admits an edge colouring with defect $d$ using (at most)
$k$ colours. In other words, the edge set can be partitioned into at most $k$
subgraphs of maximum degree $d$. The _$d$ -defective chromatic index_ of $G$
is the minimum $k$ such that $G$ is $(k,d)$-edge colourable and is denoted by
$\chi^{{}^{\prime}}_{d}(G)$. So $\chi^{\prime}_{1}(G)$ is the usual chromatic
index.

This notion is called frugal edge colouring in [2] and improper edge colouring
in [6]. Our vocabulary follows the one existing for the analogue concept of
defective vertex colouring, a now well established notion. See [16] for a nice
dynamic survey on defective vertex colouring.

Our first result is the following.

###### Theorem 1.1

Let $d,\Delta\geq 1$ and let $G$ a graph with maximum degree $\Delta$. If $d$
is even, then $\chi^{\prime}_{d}(G)=\lceil\frac{\Delta}{d}\rceil$, and if $d$
is odd, then $\chi^{\prime}_{d}(G)\leq\lceil\frac{3\Delta-1}{3d-1}\rceil$.
Moreover, these bounds are tight for every value of $\Delta$ and $d$, see
Lemma 2.7.

The case $d=1$ corresponds to the classic result of Shannon [14] on chromatic
index stating that for every graph $G$,
$\chi^{\prime}_{1}(G)\leq\lfloor\frac{3\Delta(G)}{2}\rfloor$ (observe that
$\lceil\frac{3\Delta-1}{2}\rceil=\lfloor\frac{3\Delta}{2}\rfloor$ whenever
$\Delta\geq 1$). When $d$ is even, the result is almost trivial in our context
(see Theorem 3.1, and was already known in the more general context of list
colouring [6, 2]. When $d$ is odd, a proof that
$\chi^{\prime}_{d}(G)\leq\lceil\frac{3\Delta}{3d-1}\rceil$ in the context of
list coloring is announced in [2], but seems to contain a flaw and actually
holds only in the case where $\Delta$ is divisible by $3k-1$. See section 5
for more on the list colouring context.

Vizing’s celebrated theorem on edge colouring [15] states that for every
simple graph $G$, $\chi^{\prime}_{1}(G)\in\\{\Delta(G),\Delta(G)+1\\}$, and
Holyer [8], and Leven and Galil [11] proved that deciding if
$\chi^{\prime}_{1}(G)=\Delta(G)$ is NP-complete even restricted to $d$-regular
simple graphs as soon as $d\geq 3$. We generalize both results by proving that
for every simple graph $G$,
$\chi^{\prime}_{d}(G)\in\\{\lceil\frac{\Delta}{d}\rceil,\lceil\frac{\Delta+1}{d}\rceil\\}$
(which is easily implied by Vizing’s Theorem) and we characterize the values
of $\Delta$ and $d$ for which the problem is NP-complete. More precisely, we
prove that, given a $\Delta$-regular simple graph, it is NP-complete to decide
if $\chi^{\prime}_{d}(G)=\lceil\frac{\Delta}{d}\rceil$ if and only if $d$ is
odd and $\Delta=kd$ for some $k\geq 3$. See Theorem 4.4.

We give some definitions and preliminary results in Section 2. We prove the
generalization of Shannon’s Theorem in Section 3 and the proof of the
generalization of Vizing’s Theorem in Section 4. Finally, in Section 5, we
propose as conjectures a generalisation of Theorem 1.1 for list coloring and a
generalisations of the Goldberg-Seymour Conjecture.

##  2 Definitions and preliminaries

Let $G$ be a graph. The _size_ of $G$ is its number of vertices. It is regular
if there is an integer $k$ such that every vertex of $G$ has degree $k$. In
this case we can also say it is $k$-regular. We say that $G$ is _$k$ -edge-
connected_ if it remains connected whenever (strictly) fewer than $k$ edges
are removed. If $u,v\in V(G)$, we denote as $G+uv$ the graph
$(V(G),E(G)\cup\\{uv\\})$ (recall that in this paper graphs can have multiple
edges, so if there is already an edge between $u$ and $v$, another one is
added). Similarly, $G-uv=(V(G),E(G)\setminus\\{uv\\})$.

The following gives a trivial lower bound on the $d$-defective chromatic index
that turns out to be tight whenever $d$ is even (see Theorem 3.1).

###### Lemma 2.1

For every graph $G$,
$\chi^{\prime}_{d}(G)\geq\lceil\frac{\Delta(G)}{d}\rceil$.

###### Proof.

A least $\lceil\frac{\Delta(G)}{d}\rceil$ colours are needed to colour the
edges incident to a vertex of degree $\Delta(G)$. ∎

###### Lemma 2.2

Let $k,d,\Delta$ be integers. If every $(\Delta+1)$-regular graph is
$(k,d)$-edge colourable, then every $\Delta$-regular graph is also
$(k,d)$-edge colourable.

###### Proof.

Let $G$ be a $\Delta$-regular graph. Take two disjoint copies $G^{\prime}$ and
$G^{\prime\prime}$ of $G$ and add an edge between each vertex $v\in
V(G^{\prime})$ and its copy in $G^{\prime\prime}$. The obtained graph $H$ is
$(\Delta+1)$-regular and contains $G$ as a subgraph, so
$\chi^{\prime}_{d}(G)\leq\chi^{\prime}_{d}(H)\leq k$. ∎

#### Factors in graphs

A _$k$ -factor_ of $G$ is a $k$-regular spanning subgraph of $G$. We sometimes
consider a $k$-factor $F$ as its edge set $E(F)$. We recall this theorem from
Petersen [12], one of the very first fundamental results in graph theory:

###### Theorem 2.3

[12] Let $\Delta$ be an even integer. A $\Delta$-regular graph admits a
$k$-factor for every even integer $k\leq\Delta$.

An Eulerian cycle of a graph $G$ is a cycle that uses every edge of $G$. It is
a well-known fact that a graph admits an Eulerian cycle if and only if it is
connected and all its vertices have even degree. The next two lemmas use this
fact to prove the existence of factors. This idea was already used by Petersen
to prove his theorem.

###### Lemma 2.4

Let $G$ be a connected $2k$-regular graph with an even number of edges. Then
the edges of $G$ can be partitioned into two $k$-factors.

###### Proof.

We number the edges $e_{1},e_{2},\dots,e_{2t}$ of $G$ along an Eulerian cycle
$C$ and we let $A=\\{e_{1},e_{3},\dots,e_{2t-1}\\}$ and
$B=\\{e_{2},e_{4},\dots,e_{2t}\\}$. Since consecutive edges of $C$ are
numbered with different parities and its first and last edges have distinct
parities, $A$ and $B$ are both $k$-regular. ∎

###### Lemma 2.5

Let $G$ be a connected $2k$-regular graph with an odd number of edges, and let
$e\in E(G)$. There exist two graphs $G_{A}=(V,A)$ and $G_{B}=(V,B)$ such that
$E(G)=A\cup B\cup\\{e\\}$, $\Delta(G_{A})\leq k$ and $\Delta(G_{B})\leq k$.

###### Proof.

The proof is the same as for the previous Lemma, except that we do not assign
the last edge of the Eulerian cycle, and we choose $e$ to be this last edge. ∎

The next theorem roughly says that, in a $\Delta$-regular graph, one can find
a $k$-factor as soon as $k$ is even and is relatively small compared to
$\Delta$. It was first proved in [9]. See also Theorem 3.10 $(v)$ in [1]). The
version stated here is a simplified version of the original theorem.

###### Theorem 2.6

[9] Let $\Delta$ be an odd integer and $G$ a $2$-edge connected
$\Delta$-regular graph. Let $e\in E(G)$. Let $k$ be an even integer with
$k\leq\frac{2\Delta}{3}$. Then $G$ has a $k$-factor containing $e$.

#### Shannon graphs

Given an integer $k$, the _Shannon graph_ $Sh(k)$ is the graph made of three
vertices connected by $\lfloor\frac{k}{2}\rfloor$, $\lfloor\frac{k}{2}\rfloor$
and $\lceil\frac{k}{2}\rceil$ edges respectively. See Figure 1. Observe that

  * •

$\Delta(Sh(k))=k$,

  * •

when $k$ is even, $Sh(k)$ is $k$-regular and has $\frac{3k}{2}$ edges and,

  * •

when $k$ is odd, $Sh(k)$ has two vertices of degree $k$ and one vertex of
degree $k-1$ and has $\frac{3k-1}{2}$ edges.

$\lfloor\frac{k}{2}\rfloor$$\lfloor\frac{k}{2}\rfloor$$\lceil\frac{k}{2}\rceil$
Figure 1: The Shannon graph $Sh(k)$

###### Lemma 2.7

Let $k,d\in\mathbb{N}^{*}$ with $d$ odd. Then
$\chi^{\prime}_{d}(Sh(k))=\lceil\frac{3k-1}{3d-1}\rceil$.

###### Proof.

Consider an ordering $(e_{i})_{1\leq i\leq|E(Sh(k))|}$ of the edges of $Sh(k)$
such that for any $1\leq i\leq|E(Sh(k))|-2$, $e_{i}$, $e_{i+1}$ and $e_{i+2}$
forms a triangle. Such an ordering can be obtained by setting $e_{1}$ to be
any edge with both extremities of degree $k$ and then setting, for
$i=2,\dots,|E(Sh(k))|-1$, $e_{i+1}$ to be any unnumbered edge coming right
after $e_{i}$ in clockwise order. The following statement is easily proven
using induction: _For every odd integer $\ell$ such that
$3\leq\ell\leq\frac{2|E(Sh(k)|-1}{3}$, every contiguous subsequence of
$(e_{i})_{1\leq i\leq|E(Sh(k))|}$ of length $\frac{3\ell-1}{2}$ induces a
graph of maximum degree $\ell$. _

Thus, colouring the first $\frac{3d-1}{2}$ edges of $(e_{i})_{1\leq
i\leq|E(Sh(k))|}$ in one colour, the following $\frac{3d-1}{2}$ in a second
colour and so on, yields a colouring with at most
$\lceil\frac{|E(Sh(k))|}{\frac{3d-1}{2}}\rceil$ colours such that each colour
class induces a subgraph with maximum degree at most $d$, and each colour
class except at most one has $\frac{3d-1}{2}$ edges. Since every subgraph of
$Sh(k)$ with maximum degree $d$ (recall that $d$ is odd) has at most
$\frac{3d-1}{2}$ edges, this colouring is an optimal d-defective edge
colouring and thus:

$\chi^{\prime}_{d}(Sh(k))=\Bigl{\lceil}\frac{|E(Sh(k))|}{\frac{3d-1}{2}}\Bigr{\rceil}=\begin{cases}\lceil\frac{3k}{3d-1}\rceil=\lceil\frac{3k-1}{3d-1}\rceil&\text{
if }k\text{ is even}\\\ \lceil\frac{3k-1}{3d-1}\rceil&\text{ if }k\text{ is
odd}\end{cases}$

∎

##  3 Generalization of Shannon Theorem

The goal of this section is to prove Theorem 1.1. The case where $d$ is even
was already known, we give the proof anyway for completeness.

###### Theorem 3.1

[6, 2] Let $d,\Delta\in\mathbb{N}^{*}$ with $d$ even. For every
$\Delta$-regular graph $G$,
$\chi^{{}^{\prime}}_{d}(G)=\lceil\frac{\Delta}{d}\rceil$.

###### Proof.

If $\Delta$ is even, then
$\chi^{\prime}_{d}(G)\leq\lceil\frac{\Delta(G)}{d}\rceil$ by Theorem 2.3. If
$\Delta$ is odd, then
$\lceil\frac{\Delta+1}{d}\rceil=\lceil\frac{\Delta}{d}\rceil$ and by Lemma
2.2, $\chi^{\prime}_{d}(G)\leq\lceil\frac{\Delta}{d}\rceil$. Equality holds in
both cases by Lemma 2.1. ∎

###### Theorem 3.2

Let $d,\Delta\in\mathbb{N}^{*}$ with $d$ odd. Then every graph $G$ with
maximum degree $\Delta$ is $(\lceil\frac{3\Delta-1}{3d-1}\rceil,d)$-edge
colourable.

###### Proof.

If $d=1$, then the result corresponds to the classic result of Shannon, so we
may assume that $d\geq 3$.

First observe that it is enough to prove the result for regular graphs.
Indeed, if $G$ is not $\Delta$-regular, we can build a $\Delta$-regular graph
$H$ containing $G$ as a subgraph as follows: take two copies of $G$, and for
each vertex $v$ of $G$, add $\Delta-d(v)$ edges between the two copies of $v$.
Now, if $H$ is $(\lceil\frac{3\Delta-1}{3d-1}\rceil,d)$-edge colourable, then
$G$ is too. Moreover, by Lemma 2.2, it is enough to prove it for values of
$\Delta$ such that
$\lceil\frac{3\Delta-1}{3d-1}\rceil<\lceil\frac{3(\Delta+1)-1}{3d-1}\rceil$.
We call such integers special.

Let $G$ be a counterexample that minimizes $\Delta$ and has minimum size. That
is, $\Delta$ is special, $G$ is $\Delta$-regular,
$\chi^{\prime}_{d}(G)=\lceil\frac{3\Delta-1}{3d-1}\rceil+1$, every
$\Delta$-regular graph with less vertices than $G$ is
$(\lceil\frac{3\Delta-1}{3d-1}\rceil,d)$-edge colourable, and for every
special integer $\Delta^{\prime}<\Delta$, every $\Delta^{\prime}$-regular
graph is $(\lceil\frac{3\Delta^{\prime}-1}{3d-1}\rceil,d)$-edge colourable.
The result is trivial when $\Delta\leq 2$, so we can also assume $\Delta\geq
3$.

(1) If $G$ has a bridge $e$, then a connected component of $G-e$ is isomorphic
to $Sh(\Delta)$.

Set $e=ab$ and let $A$ and $B$ be the two connected components of $G-e$
containing $a$ and $b$ respectively. Assume for contradiction that neither $A$
nor $B$ is isomorphic to $Sh(\Delta)$. Vertices of $A$ have degree $\Delta$ in
$A$ except for $a$ that has degree $\Delta-1$. Hence, we cannot have
$|V(A)|\in\\{1,2\\}$, nor $|V(A)|=3$ as otherwise $A$ is isomorphic to
$Sh(\Delta)$. We can thus assume $|V(A)|\geq 4$.

Let $G_{A}$ be the graph obtained from $G$ by replacing $A$ by $Sh(\Delta)$ as
in Figure 2. $G_{A}$ is $\Delta$-regular and has strictly less vertices then
$G$. Hence, by minimality of $G$, $G_{A}$ admits an edge colouring $c_{A}$
with defect $d$ using at most $\lceil\frac{3\Delta-1}{3d-1}\rceil$ colours. We
define symmetrically $G_{B}$ and $c_{B}$. We may assume, by properly permuting
colours in $G_{B}$, that $c_{B}(e)=c_{A}(e)$. We can now obtain an edge
colouring of $G$ with defect $d$ using at most
$\lceil\frac{3\Delta-1}{3d-1}\rceil$ colours by assigning colour $c_{A}(e)$ to
$e$, colour $c_{A}(e^{\prime})$ to any edge $e^{\prime}$ in $B$ and colour
$c_{B}(e^{\prime})$ to any edge $e^{\prime}$ in $A$. This proves (1).

$a$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor$$\lceil\frac{\Delta}{2}\rceil$B$b$
Figure 2: the graph $G_{A}$

Observe that, if a $\Delta$-regular graph has a bridge, then $\Delta$ must be
odd. Moreover, if $\Delta$ is odd, for every $(\frac{3\Delta-1}{3d-1},d)$ edge
colouring of $Sh(\Delta)$, there is a colour $c$ such that the (unique) vertex
of $Sh(\Delta)$ with degree $\Delta-1$ is incident with at most $d-1$ edges
coloured with $c$. This simple observation is used in the proof of the
following claim.

(2) $G$ has at most one bridge.

Suppose for contradiction that $G$ has two bridges $uv$ and
$u^{\prime}v^{\prime}$. By (3), we may assume that $G$ is made of two disjoint
copies of $Sh(\Delta)$ plus a graph $A$ as in Figure 3 (note that
$u=u^{\prime}$ is possible. See Figure 4).

Assume first that $u\neq u^{\prime}$. Then $A+uu^{\prime}$ is $\Delta$-regular
and has strictly less vertices than $G$. So $A+uu^{\prime}$ admits an edge
colouring $c_{A}$ with defect $d$ using at most
$\lceil\frac{3\Delta-1}{3d-1}\rceil$ colours. We can extend this colouring to
$G$ by giving colour $c_{A}(uu^{\prime})$ to $uv$ and $u^{\prime}v^{\prime}$
and then extend this colouring to the two copies of $Sh(\Delta)$ (this is
possible by the observation stated right before the claim).

$v$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor$$\lceil\frac{\Delta}{2}\rceil$A$u$$v^{\prime}$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor$$\lceil\frac{\Delta}{2}\rceil$$u^{\prime}$
Figure 3: the graph $G$ when $u\neq u^{\prime}$

Assume now that $u=u^{\prime}$. We consider the graph $G^{\prime}$ obtained by
replacing the two copies of $Sh(\Delta)$ by four new vertices as in Figure 4.
As $G^{\prime}$ is $\Delta$-regular and has two vertices less then $G$, it is
$(\lceil\frac{3\Delta-1}{3d-1}\rceil,d)$-colourable. The obtained colouring of
$A$ can easily be extended to the two copies of $Sh(\Delta)$ without any new
colour (this is again possible by the observation stated right before the
claim). This proves (2).

$v$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor$$\lceil\frac{\Delta}{2}\rceil$A$u$$v^{\prime}$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor$$\lceil\frac{\Delta}{2}\rceil$$u$A$w$$x$$y$$z$$\lfloor\frac{\Delta}{2}\rfloor$-$1$$\lfloor\frac{\Delta}{2}\rfloor$-$1$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor$
Figure 4: On the right: the graph $G$ when $u=u^{\prime}$, on the left: the
graph $G^{\prime}$.

(3) $G$ has a $k$-factor for every even integer $k\leq\frac{2\Delta}{3}$.

Let $k\leq\frac{2\Delta}{3}$ be an even integer. If $\Delta$ is even, the
result holds by Theorem 2.3. So we may assume that $\Delta$ is odd. If $G$ is
$2$-edge connected, then we are done by Theorem 2.6. So assume $G$ has a
bridge $uv$. Let $A,B$ be the two connected components of $G\setminus uv$ with
$u\in V(A)$ and $v\in V(B)$. By (3), $G$ has no other bridges and thus $A$ and
$B$ are both $2$-edge-connected. By (3), one of $A$ or $B$ is isomorphic to
$Sh(\Delta)$. Without loss of generality, we suppose that it is $B$. Let $w$
and $x$ be the two other vertices of $B$. Let $y$ be a neighbour of $u$ in
$A$. Consider $G^{\prime}=G+uv+yw-uy-vw$ (see Figure 5). It is easy to check
that $G^{\prime}$ is $\Delta$-regular and $2$-edge-connected. Applying Theorem
2.6 on $G^{\prime}$ with $e=wy$, $G^{\prime}$ has a $k$-factor $F$ containing
the edge $wy$. There exists an integer $s\leq k-1$ such that $F$ contains $s$
edges $wx$, and $k-s-1$ edges $wv$. So $F$ must contain $k-s$ edges $vx$ and
thus $F$ contains exactly one edge $uv$. Hence, $F-uv-yw+uy+vw$ is a
$k$-factor of $G$. This proves (3).

$v$$x$$w$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor$$\lceil\frac{\Delta}{2}\rceil$A$u$$y$$v$$x$$w$$\lfloor\frac{\Delta}{2}\rfloor$$\lfloor\frac{\Delta}{2}\rfloor{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}-1}$$\lceil\frac{\Delta}{2}\rceil$A$u$$y$
Figure 5: The graphs $G$ and $G^{\prime}$

Having established the three claims (1), (2) and (3), we can proceed to prove
the theorem. We begin by treating the five smallest special values of
$\Delta$.

Case 1: $\lceil\frac{3\Delta-1}{3d-1}\rceil=1$, $\Delta=d$. The result holds
trivially.

Case 2: $\lceil\frac{3\Delta-1}{3d-1}\rceil=2$, $\Delta=2d-1$. We can apply
(3) with $k=d-1$ to get a $(d-1)$-factor of $G$, whose complementary in $G$ is
a $d$-factor. Thus $\chi^{\prime}_{d}(G)\leq 2$. This proves case 2.

Case 3: $\lceil\frac{3\Delta-1}{3d-1}\rceil=3$, $\Delta=3d-1$. Observe that
$\Delta$ is even. By Theorem 2.3, $G$ has a $2d$-factor $F$. By applying Lemma
2.4 on connected components of even size of $F$ and Lemma 2.5 on connected
components of odd size, we can extract graphs $G_{A}$ and $G_{B}$ along with a
matching $M$ such that $E(F)=E(G_{A})\cup E(G_{B})\cup M$, $\Delta(G_{A})\leq
d$, $\Delta(G_{B})\leq d$. Now, $E(G)$ can be partitioned into $E(G_{A})$,
$E(G_{B})$ and $E(G)\cup M\setminus F$, each of these sets having maximum
degree at most $d$. This proves case 3.

Case 4: $\lceil\frac{3\Delta-1}{3d-1}\rceil=4$, $\Delta=4d-1$. By applying (3)
with $k=2d$, we get a $2d$-factor $A$ of $G$, whose complementary in $G$ is a
$(2d-1)$-factor $B$. By applying Lemma 2.4 on components of $A$ of even size
and Lemma 2.5 on components of $A$ of odd size, we get $A=A_{1}\cup A_{2}\cup
M$ where $\Delta(A_{1})\leq d$, $\Delta(A_{2})\leq d$ and $M$ is a matching.

It remains to prove that $\chi^{\prime}_{d}(B\cup M)\leq 2$. Let $C$ be a
connected component of $B\cup M$. If every vertex of $C$ is incident with an
edge of $M$, then $C$ has an even number of vertices and is $2d$-regular, and
so $\chi^{\prime}_{d}(C)=2$ by Lemma 2.4. Assume now that there exists a
vertex of $C$ that is not incident with an edge of $M$. Take two copies of
$C$, and add an edge between the copies of each vertex of $C$ not incident
with an edge of $M$. The obtained graph has an even number of vertices and is
$2d$-regular, so it is $(2,d)$-edge colourable by Lemma 2.4 and thus so is
$C$. So each connected component of $B\cup M$ is $(2,d)$-edge colourable, and
thus so is $B\cup M$. This proves case 4.

Case 5: $\lceil\frac{3\Delta-1}{3d-1}\rceil=5$, $\Delta=5d-2$. By applying (3)
with $k=3d-1$, we can partition $G$ into a $(2d-1)$-factor $A$ and a
$(3d-1)$-factor $B$. By respectively using cases 2 and 3, we have
$\chi^{\prime}_{d}(A)\leq 2$ and $\chi^{\prime}_{d}(B)\leq 3$, so
$\chi^{\prime}_{d}(G)\leq 5$. This proves case 5.

We may now assume that $\Delta\geq 5d-1$. If $\Delta$ is even, then $G$ has a
$(3d-1)$-factor by Petersen Theorem (2.3), and if $\Delta$ is odd, since
$3d-1\leq\frac{2(5d-1)}{3}=\frac{2\Delta}{3}$ and $3d-1$ is even, $G$ admits a
$(3d-1)$-factor by (3). Let $F$ be a $(3d-1)$-factor of $G$. By Case 3, $F$ is
$(3,d)$-edge colourable. As $G-F$ is $(\Delta-(3d-1))$-regular, by minimality
of $\Delta$ we have:

$\chi^{\prime}_{d}(G-F)\leq\lceil\frac{3(\Delta-(3d-1))-1}{3d-1}\rceil,$

and thus

$\chi^{\prime}_{d}(G)\leq
3+\lceil\frac{3(\Delta-(3d-1))-1}{3d-1}\rceil=\lceil\frac{3\Delta-9d+3-1+9d-3}{3d-1}\rceil=\lceil\frac{3\Delta-1}{3d-1}\rceil.$

∎

##  4 Generalization of Vizing Theorem

In this section, we will only consider simple graphs. Vizing [15] proved the
following theorem :

######  Theorem 4.1 (Vizing’s Theorem, [15])

For every simple graph $G$ with maximum degree $\Delta$,
$\chi^{\prime}_{1}(G)\in\\{\Delta,\Delta+1\\}$.

While there are only $2$ possibilities, deciding between them was proven to be
NP-complete even for regular simple graphs.

######  Theorem 4.2 ( Holyer [8], Leven and Galil [11])

For every $\Delta\geq 3$, it is NP-complete to decide if a $\Delta$-regular
simple graph $G$ is $\Delta$-edge colourable.

Vizing’s theorem easily implies its following generalization to $d$-defective
edge colouring.

###### Corollary 4.3

For every $d\geq 1$ and every simple graph $G$ with maximum degree $\Delta$,
$\chi^{\prime}_{d}(G)\in\\{\lceil\frac{\Delta}{d}\rceil,\lceil\frac{\Delta+1}{d}\rceil\\}$.

###### Proof.

The lower bound holds by Lemma 2.1. For the upper bound, consider an edge
colouring of $G$ with $\Delta(G)+1$ colours (it exists by Vizing’s Theorem)
and let $M_{1},\dots,M_{\Delta(G)+1}$ be the classes of colours. By assigning
colour $1$ to $M_{1}\cup\dots\cup M_{d}$, colour $2$ to $M_{d+1}\cup\dots\cup
M_{2d}$, etc, we obtain a $(\lceil\frac{\Delta+1}{d}\rceil,d)$ edge colouring
of $G$. ∎

We now prove a generalization of Theorem 4.2 in the context of defective edge
colouring. Before that, we need the following construction.

For every integer $k,d\geq 1$, we construct a simple graph $G_{kd,d}$ such
that $G$ is $kd$-regular and $\chi^{\prime}_{d}(G)=k$. We can set
$G_{d,d}=K_{d+1}$. Inductively, having defined $G_{kd,d}$, let $G_{(k+1)d,d}$
be the simple graph obtained by taking two disjoint copies of $G_{kd,d}$ and
adding the edges of any $d$-regular bipartite simple graph between these two
copies111For example, naming $u_{1},\dots,u_{n}$ and $v_{1},\dots,v_{n}$ the
vertices of the two copies of $G_{kd,d}$, add the edges
$u_{i}v_{i},u_{i}v_{i+1},\dots,u_{i}v_{i+d}$ for $i=1,\dots,n$, subscripts
being taken modulo $n$. It gives a $d$-regular bipartite simple graph as soon
as $n\geq d$.. The obtained simple graph is clearly $(k+1)d$-regular, and we
can $(k+1,d)$-edge colour it by taking a $(k,d)$-edge colouring for the two
copies of $G_{kd,d}$ and add a new colour for the added edges, and finally by
Lemma 2.1 it does not admit a $(k,d)$-edge colouring. Hence
$\chi^{\prime}_{d}(G_{(k+1)d,d})=k+1$.

###### Theorem 4.4

Let $d,\Delta\geq 1$, and $G$ a simple graph with maximum degree $\Delta$.
Then $\chi^{\prime}_{d}(G)=\lceil\frac{\Delta}{d}\rceil$ if:

  * •

$d$ does not divide $\Delta$ or,

  * •

$d$ is even or,

  * •

$\Delta=d$ or,

  * •

$\Delta=2d$ and every $2d$-regular connected component of $G$ has an even
number of vertices.

Moreover, if $d$ is odd, $\Delta=2d$ and a $2d$-regular connected component of
$G$ has an odd number of vertices, then $\chi^{\prime}_{d}(G)=3$. Finally, in
every other case, that is if $d$ is odd and $\Delta=kd$ for some $k\geq 3$, it
is NP-complete to decide if $\chi^{\prime}_{d}(G)=k$.

###### Proof.

The first case is a direct consequence of Corollary 4.3, noticing that if $d$
does not divide $\Delta$, then
$\lceil\frac{\Delta(G)}{d}\rceil=\lceil\frac{\Delta(G)+1}{d}\rceil$. The
second case has already been proven. See Theorem 3.1. The third case is
trivial. To prove the fourth case, take two disjoint copies of $G$, and for
each vertex $v$ of $G$, add $2d-d(v)$ edges between the two copies of $v$. The
obtained (not necessarily simple) graph $G^{\prime}$ is $2d$-regular, and each
of its connected component has even size (as the connected components of odd
size of $G$ were not regular and thus are included in connected components of
even size of $G^{\prime}$). Now, by Lemma 2.4, $G^{\prime}$ is $(2,d)$-edge
colourable, and so is $G$.

Assume now that $d$ is odd, $\Delta=2d$, and $G$ has a $2d$-regular connected
component $C$ of odd size. As $C$ is of odd size and $d$ is odd, $G$ does not
admit a $d$-factor, and thus cannot be $(2,d)$ edge coloured. So, by Corollary
4.3, $\chi^{\prime}_{d}(G)=3$.

Finally, assume that $d$ is odd and $\Delta=kd$ for some integer $k\geq 3$.
Deciding if $\chi^{\prime}_{d}(G)=k$ is clearly in NP. We perform a reduction
from the case $d=1$ (which is NP-complete by Theorem 4.2). Let $G$ be a
$k$-regular simple graph.

We construct a simple graph $G^{\prime}$ as follows: start with a copy of $G$,
then for each vertex $v$ of $G$, add $\frac{k(d-1)}{2}$ disjoint copies of
$G_{kd,k}$, remove one edge $ab$ and add edges $av$ and $bv$ for each copy.
The graph $G^{\prime}$ is clearly simple, and $kd$-regular.

We now prove that $\chi^{\prime}_{1}(G)=k$ if and only if
$\chi^{\prime}_{d}(G^{\prime})=k$. Assume first that there exists a $(k,1)$
edge colouring of $G$ using $k$ colours and let us show how to find a
$(k,d)$-edge colouring of $G^{\prime}$, which would imply that
$\chi^{\prime}_{d}(G)=k$ by Corollary 4.3. We use colours from
$\\{1,2,\dots,k\\}$. Start with a $(k,1)$ edge colouring of the copy of $G$ in
$G^{\prime}$. Observe that each vertex is incident with exactly one edge of
each colour. For every vertex $u$ in the copy of $G$, and for
$i=1,2,\dots,\frac{k(d-1)}{2}$, assign colour $1+(i\mod k)$ to the two edges
linking $u$ and the $i^{th}$ copy $G_{kd,k}$ (after we have removed an edge).
Now, each vertex $u$ in the copy of $G$ is incident with precisely $d$ edges
of each colour. It remains to extend the colouring to the copies of $G_{kd,d}$
(after we have removed an edge) which can easily be done since
$\chi^{\prime}_{d}(G_{kd,d})=k$ and for each copy, naming $ab$ the missing
edge, each of $a$ and $b$ is incident with a single coloured edge, both of the
same colour.

We now assume that $\chi^{\prime}_{d}(G^{\prime})=k$. We are going to show
that in any $(k,d)$-edge colouring of $G^{\prime}$, the copy of $G$ in
$G^{\prime}$ is $(k,1)$-edge coloured, implying that $\chi^{\prime}_{1}(G)=k$
by Vizing Theorem. So let us start with a $(k,d)$ edge colouring of
$G^{\prime}$. Let $u$ be a vertex in the copy of $G$ in $G^{\prime}$, and let
$C$ be one of the $\frac{k(d-1)}{2}$ copies of $G_{kd,d}$ (from which we have
removed an edge) linked with $u$. We name $a$ and $b$ the vertices in $C$
incident with the missing edge and observe that in $C$, each vertex has degree
$kd$ except for $a$ and $b$ that have degree $kd-1$. Since
$|E(C)|=\frac{kd|V(C)|}{2}-1$ and each colour class covers at most
$\frac{d|V(C)|}{2}$ edges of $C$, it must be that each colour class covers
$\frac{d|V(C)|}{2}$ edges of $C$, that is each colour class induces a
$d$-regular simple graph, except for one colour class that covers only
$\frac{d|V(C)|}{2}-1$ edges. Naming $c$ this colour, we get that vertices $a$
and $b$ are incident with exactly $d-1$ edges coloured $c$, and $d$ edges of
every other colour. So the edges $au$ and $bv$ must receive the colour $c$.

In particular, for each copy of $G_{kd,d}$ linked with $u$, the two edges
linking $u$ with this copy must receive the same colour. Moreover, each colour
must appear between $u$ and precisely $\frac{d-1}{2}$ copies of $G_{kd,d}$,
for otherwise $u$ would be incident with more than $d$ edges of a given
colour. Hence, each colour appears $d-1$ times in the $k(d-1)$ edges linking
$u$ with the copies of $G_{kd,d}$ and thus each colour appears exactly once in
the $k$ edges incident with $u$ in the copy of $G$. Hence, as announced, the
$(k,d)$-edge colouring of $G^{\prime}$ induces a $(k,1)$-edge colouring of
$G$. ∎

We point out that Vizing[15] also proved that for every (not necessarily
simple) graph $G$ with maximum degree $\Delta$ and edge multiplicity $\mu$,
$\chi^{\prime}_{1}(G)\leq\Delta+\mu$ where the edge multiplicity is the
maximum number of edges between two vertices. This directly implies that
$\chi^{\prime}_{d}(G)\leq\lceil\frac{\Delta+\mu}{d}\rceil$.

##  5 Further works

### List colouring

The $d$-defective list chromatic index of a graph $G$, denoted by
$ch^{\prime}_{d}(G)$, is defined as the minimum $k$ such that, for any choice
of list of $k$ integers given to each edge, there is an edge colouring with
defect $d$ such that each edge receives a colour from its list. So
$ch^{\prime}_{1}(G)$ is the usual list chromatic index.

Borodin et al. [3] proved that Shannon bound holds for the list chromatic
index, that is, for every graph $G$,
$ch_{1}^{\prime}(G)\leq\lceil\frac{3\Delta(G)}{2}\rceil$. It is then natural
to ask if Theorem 1.1 extends to defective list edge colouring. As mention in
the introduction, when $d$ is even, it is proved in [6] (and a simpler proof
is given in [2]) that for every graph $G$,
$ch^{\prime}_{d}(G)=\lceil\frac{\Delta(G)}{d}\rceil$. When $d$ is odd, a proof
that $chi^{\prime}_{d}(G)\leq\lceil\frac{3\Delta}{3d-1}\rceil$ is announced in
[2] but seems to have a flaw and actually holds only in the case where
$\Delta$ is divisible by $3k-1$.

###### Conjecture 5.1

For every odd integer $d$ and for every graph $G$,
$ch^{\prime}_{d}(G)\leq\lceil\frac{3\Delta-1}{3d-1}\rceil$

We finally mention the following stronger conjecture that corresponds to the
infamous list edge colouring conjecture for $d=1$ and is proved for bipartite
graph in [6].

###### Conjecture 5.2

[7] For every graph $G$ and every integer $d$,
$ch^{\prime}_{d}(G)=\chi^{\prime}_{d}(G)$.

### The Goldberg-Seymour Conjecture

Let $d\in\mathbb{N}^{*}$ and $G$ a graph. Observe that in any edge-coloring of
$G$ with defect $d$, and for any $X\subseteq V(G)$, each color class contains
at most $\lfloor\frac{d|X|}{2}\rfloor$ edges, which leads to the following
lower bound on the $d$-defective edge chromatic number of any graph $G$:

$\chi^{\prime}_{d}(G)\leq\Gamma_{d}(G)=\max\Big{\\{}\Bigl{\lceil}\frac{|E(G[X])|}{\lfloor\frac{d|X|}{2}\rfloor}\Bigr{\rceil}\mid
X\subseteq V(G)\Big{\\}}.$

The following was known as the Goldberg-Seymour Conjecture [5, 13] for almost
50 years. Recently, Chen et al. [4] announced a proof.

######  Conjecture 5.3 (Golberg-Seymour [5, 13])

For every graph $G$,
$\chi^{\prime}_{1}(G)\leq\max\\{\Gamma_{1}(G),\Delta(G)+1\\}$.

We think that the following generalization could hold.

###### Conjecture 5.4

Every graph $G$ satisfies
$\chi^{\prime}_{d}(G)\leq\max\\{\Gamma_{d}(G),\lceil\frac{\Delta(G)+1}{d}\rceil\\}$.

An easy proof of the conjecture could start as follows. A counter-example $G$
to the conjecture must satisfy
$\Delta(G)+1<\chi^{\prime}_{1}(G)=\Gamma_{1}(G)$. This implies that
$\chi^{\prime}_{d}(G)\leq\lceil\frac{\Gamma_{1}(G)}{d}\rceil$. So it is enough
to prove that
$\lceil\frac{\Gamma_{1}(G)}{d}\rceil\leq\max\\{\Gamma_{d}(G),\lceil\frac{\Delta(G)+1}{d}\rceil\\}$.
Unfortunately this last inequality does not hold, for example on the following
simple example. Consider the graph $G$ made of three vertices connected by
respectively $7$, $7$ and $2$ edges. The followings hold:

$15=\Delta(G)+1<\Gamma_{1}(G)=\chi^{\prime}_{1}(G)=16,$

whereas

$4=\Gamma_{3}(G)<\lceil\frac{\Delta(G)+1}{3}\rceil=\chi^{\prime}_{3}(G)=5.$

### The degree Ramsey number of stars

In this subsection, we briefly describe the link between the degree Ramsey
number of stars and defective edge colouring. We are thankfull to Ross Kang
for bringing this to our attention.

Let $H$, $G$ be simple graphs. Let $H\rightarrow_{s}G$ means that every
colouring of $E(H)$ with $s$ colours produces a monochromatic copy of $H$. The
degree Ramsey number of a simple graph $G$ is
$R_{\Delta}(G;s)=\min\\{\Delta(H):H\rightarrow_{s}G\\}$. Observe that
$H\rightarrow_{s}K_{1,d+1}$ means that $\chi^{\prime}_{d}(H)\geq s+1$. Hence,
$R_{\Delta}(K_{1,d+1};s)=\min\\{\Delta(H):\chi^{\prime}_{d}(H)\geq s+1\\}$.

It can be proved (with a little brain gymnastic) that the following result of
Kinnersley, Milans and West is equivalent to corollary 4.3.

###### Theorem 5.5

[10] If $s\geq 2$, then
$R_{\Delta}(K_{1,d+1};s)=\left\\{\begin{array}[]{ll}s\cdot d&\mbox{if }d\mbox{
is odd}\\\ s\cdot d+1&\mbox{if }d\mbox{ is even}\end{array}\right.$

It could be of interest to look at the degree Ramsey number of (multi)graphs.

Acknowledgment: This work was supported by the group Casino/ENS Chair on
Algorithmics and Machine Learning.

## References

  * [1] Jin Akiyama and Mikio Kano.  Factors and Factorizations of Graphs Proof Techniques in Factor Theory, volume 2031.  Springer, 2011.
  * [2] Omid Amini, Louis Esperet, and Jan Van Den Heuvel.  Frugal Colouring of Graphs.  Research Report RR-6178, INRIA, 2007.
  * [3] O.V. Borodin, A.V. Kostochka, and D.R. Woodall.  List edge and list total colourings of multigraphs.  J. Comb. Theory Ser. B, 71(2):184–204, nov 1997.
  * [4] Guantao Chen, Guangming Jing, and Wenan Zang.  Proof of the goldberg-seymour conjecture on edge-colorings of multigraphs, 2019.
  * [5] M. K. Goldberg.  On multigraphs of almost maximal chromatic class (russian).  Diskret. Analiz., 23, 1973.
  * [6] A.J.W. Hilton.  Aspects of edge list-colourings.  Discrete Mathematics, 231(1):253–264, 2001.  BBC17.
  * [7] A.J.W. Hilton, D.S.G. Stirling, and T. Slivnik.  A vertex-splitting lemma, de werra’s theorem, and improper list colourings.  J. Comb. Theory Ser. B, 72(1):91–103, jan 1998.
  * [8] Ian Holyer.  The np-completeness of edge-coloring.  SIAM J. Comput., 10:718–720, 1981.
  * [9] Mikio Kano.  Graph factors with given properties.  In Khee Meng Koh and Hian Poh Yap, editors, Graph Theory Singapore 1983, pages 161–168, Berlin, Heidelberg, 1984. Springer Berlin Heidelberg.
  * [10] WILLIAM B. KINNERSLEY, KEVIN G. MILANS, and DOUGLAS B. WEST.  Degree ramsey numbers of graphs.  Combinatorics, Probability and Computing, 21(1-2):229–253, 2012\.
  * [11] Daniel Leven and Zvi Galil.  Np completeness of finding the chromatic index of regular graphs.  Journal of Algorithms, 4(1):35–44, 1983.
  * [12] Julius Petersen.  Die Theorie der regulären graphs.  Acta Mathematica, 15(none):193 – 220, 1900.
  * [13] P. D. Seymour.  On multi-colourings of cubic graphs, and conjectures of fulkerson and tutte.  Proceedings of the London Mathematical Society, s3-38(3):423–460, 1979.
  * [14] Claude E. Shannon.  A theorem on coloring the lines of a network.  Journal of Mathematics and Physics, 28(1-4):148–152, 1949.
  * [15] V. G. Vizing.  Np-completeness of finding the chromatic index of regular graphs.  Diskret. Analiz., 3, 1964.
  * [16] David R. Wood.  Defective and clustered graph colouring, 2018.