%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*{J. Narboni : De la conjecture de Vizing sur la Kempe-équivalence des $(\chi'+1)$-colorations d'arêtes.}
%

% Pour le sommaire
\addcontentsline{toc}{section}{J. Narboni : De la conjecture de Vizing sur la Kempe-équivalence des $(\chi'+1)$-colorations d'arêtes.}
%

% Pour la liste des auteurs
\index{Narboni, J.}
%

% Citer un par un les auteurs et leur affiliation
\indent
\underline{Jonathan Narboni}, LaBRI, Bordeaux, {\tt jonathan.narboni@labri.fr}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

Dans son papier fondateur de 1964 \cite{V64}, Vizing prouve que $\Delta+1$ couleurs suffisent pour colorer les arêtes d'un graphe, $\Delta$ étant le degré maximum du graphe. La preuve donne en réalité un algorithme pour passer de n'importe quelle coloration à une $(\Delta+1)$-coloration via une série de changements de Kempe. Effectuer un changement de Kempe consiste à échanger les deux couleurs dans une composante bichromatique maximale.

Peu après \cite{V65}, Vizing demande si $(\Delta+1)$ peut être remplacé par le nombre optimal de couleurs $\chi'$ dans l'énoncé ci-dessus.
% pose la question s'il est toujours possible de reconfigurer une coloration à l'aide de changements de Kempe pour obtenir une coloration n'utilisant que $\chi'$ couleurs (où $\chi'$ est le nombre optimal de couleurs).
Il y a peu de classes de graphes pour lesquelles cette conjecture a été prouvée : les graphes bipartis \cite{A2009}, les graphes de degré maximum $4$, ainsi que les graphes sans triangles \cite{BO2021} .

Nous prouvons que la conjecture est vraie dans le cas des graphes sans $K_5$ et discutons de comment étendre la méthode au cas général. L'outil principal est une analyse fine des éventails de Vizing.

\smallskip


% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %Eventuellement, une figure, pdf ou png (PAS eps)
% \begin{figure}[htb]
% \begin{center}
% \includegraphics[height=3cm]{gtree}
% \caption{Un graphe.
% \label{fig:graphe}}
% \end{center}
% \end{figure}
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Vous pouvez également ajouter des références, comme~\cite{nk1} ci-dessous.



\begin{thebibliography}{99}
  
\bibitem{V64}
V.~Vizing, \emph{On an estimate of the chromatic class of a p-graph}, Discret Analiz {\bf 3} (1964), 25--30.

\bibitem{V65}
V.~Vizing, \emph{The chromatic class of a multigraph}, Cybernetics {\bf 3} (1965), 32--41.

\bibitem{A2009}
A.~Asratian, \emph{A note on transformations of edge colorings of bipartite graphs}, Journal of Combinatorial Theory, Series B  {\bf 99} (2009), 814--818.

\bibitem{B2012}
J.~McDonald, B.~Mohar, D.~Scheide, \emph{Kempe Equivalence of Edge-Colorings in Subcubic and Subquartic Graphs}, Journal of Graph theory {\bf 70} (2012), 226--239.

\bibitem{A2016}
A.~Asratian, C.~Casselgren, \emph{Solution of Vizing's Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results}, Journal of Graph Theory {\bf 82} (2016), 350--373.

\bibitem{BO2021}
M.~Bonamy, O.~Defrain, T.~Klimo{\v{s}}ov{\'a}, A.~Lagoutte, J.~Narboni, \emph{On Vizing's edge colouring question}, arXiv preprint arXiv:2107.07900


\end{thebibliography}


\vfill
\end{document}