%Compiler avec pdflatex, le résultat ne doit pas dépasser une page
%Merci de respecter scrupuleusement ce modèle.
\documentclass[a4paper,titlepage,12pt,normalheadings,makeidx]{article}
\usepackage{graphicx} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Vizing's and Shannon's Theorems for edge-defective colouring}
%

% Pour le sommaire
\addcontentsline{toc}{section}{B. Névole et A. Nonyme : Une nouvelle borne sur un
  paramètre de graphes}
%

% Pour la liste des auteurs
\index{Aubian, G.}\index{Aboulker, P.}\index{Huang, C.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Guillaume Aubian}, IRIF-Talgo, Paris {\tt aubian@ens.fr}\\
\indent
Pierre Aboulker, Talgo, Paris, {\tt pierreaboulker@gmail.com}\\ %souligner l'orateur
\indent
Chien-Chung Huang, Talgo, Paris, {\tt Chien-Chung.Huang@ens.fr}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé
For a given multigraph $G$ and integer $d$, $\chi'_{d}(G)$ is the minimum size of a partition of $G$'s edges into subgraphs of maximum degree at most $d$. Note that for $d = 1$ this corresponds to the chromatic index of $G$.

%We call a multigraph $G$ $(k,d)$-edge-defective-colourable if its edge set can be partitioned into  $k$ subgraphs of maximum degree at most $d$.  The \emph{$d$-defective chromatic index} of $G$ is the minimum $k$ such that $G$ is $(k,d)$-edge-colourable and is denoted by $\chi^{'}_{d}(G)$.

We prove that for every integer $d$, every multigraph $G$ with maximum degree $\Delta$ satisfies $\chi^{'}_{d}(G) \leq \lceil \frac{\Delta}{d} \rceil$ if $d$ is even and $\chi^{'}_{d}(G) \leq \lceil \frac{3\Delta - 1}{3d - 1} \rceil$ if $d$ is odd and that these bounds are tight. This generalizes a result from Shannon in
\cite{S49} stating that for any multigraph $G$, $\chi'_{1}(G) \leq \frac{3\Delta(G)}{2}$.


\smallskip

We also prove that for every simple graph $G$, $\chi'_{d}(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(G)$, thus generalizing the infamous Vizing's theorem (see \cite{V64}) and the corresponding NP-completeness result of Leven and Galil in \cite{LZ83}.


\begin{thebibliography}{99}


\bibitem{S49}
C. Shannon,
\newblock A Theorem on Coloring the Lines of a Network. 
\newblock {\em Studies in Applied Mathematics, Volume 28, Issue 1-4, April 1949, Pages 148-152.}


\bibitem{V64}
 V. G. Vizing,
\newblock On an estimate of the chromatic class of a p-graph. 
\newblock {\em Diskret. Analiz.}, \textbf{3}:25-30, 1964). [In Russian]


\bibitem{LZ83}
D. Leven and Galil Z.
\newblock NP-completeness of finding the chromatic index of
regular graphs. 
\newblock {\em Journal of Algorithms}, \textbf{4}:35–44, 1983.




\vfill
\end{thebibliography}

\end{document}

