%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*{H. La et M. Montassier: La coloration à distance 2 des graphes épars avec la méthode du potentiel}
%

% Pour le sommaire
\addcontentsline{toc}{section}{H. La et M. Montassier: La coloration à distance 2 des graphes épars avec la méthode du potentiel}
%

% Pour la liste des auteurs
\index{La, H.}\index{Montassier, M.}
%

% Citer un par un les auteurs et leur affiliation
\underline{Hoang La}, LIRMM, Université de Montpellier, CNRS, Montpellier, France, {\tt xuan-hoang.la@lirmm.fr}\\
\indent
Mickael Montassier, LIRMM, Université de Montpellier, CNRS, Montpellier, France, {\tt mickael.montasser@lirmm.fr}\\ %souligner l'orateur
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

Une \emph{k-coloration à distance 2} d'un graphe $G=(V,E)$ est une $k$-coloration des sommets telle que toute paire de sommets à distance au plus 2 reçoivent des couleurs différentes. Le \emph{nombre chromatique à distance 2} de $G$, noté $\chi^2(G)$, est le plus petit entier $k$ tel que $G$ admet une $k$-coloration à distance 2. Dans le cas général, $\Delta(G)\leq\chi^2(G)\leq \Delta^2(G)+1$ où $\Delta(G)$ est le degré maximum du graphe. Un exemple atteignant le majorant est entre autres le graphe de Petersen. L'étude des graphes épars est devenu un sujet de recherche actif, motivé par le passage du majorant quadratique à un majorant linénaire de la forme $\chi^2(G)\leq \Delta(G)+c$ pour une petite constante $c$.

On montre le résultat suivant : \emph{si $G$ est un graphe de degré moyen maximum au plus 18/7 et de degré maximum au moins 7, alors $\chi^2(G)\leq \Delta+1$}. Ce résultat améliore celui de Bonamy, Lévêque, et Pinlou~\cite{BLP14}. 

La plupart des résultats dans ce domaine utilise la méthode du décharge\-ment qui à la base est un comptage des objets du graphe dépendant du degré moyen maximum. Les améliorations dans le domaine passe par l'accroissement du nombre de \emph{configurations réductibles} (les structures qui ne peuvent pas apparaître dans un contre-exemple minimal) sur la classe considérée. Plus on est capable d'exhiber des configurations réductibles (dépendant principalement du nombre de couleurs), plus il est possible d'affiner les paramètres du problèmes (majorant sur le dégré moyen maximum, minorant sur le degré maximum). La méthode du potentiel introduit une fonction qui permet de quantifier et manipuler plus précisément le degré moyen maximum. Elle permet notamment de préciser le degré moyen maximum dans le voisinage de certaines configurations, ce qui permet leur réduction.

\smallskip

\begin{thebibliography}{99}

\bibitem{BLP14}
M.~Bonamy, B.~L{\'e}v{\^e}que, and A.~Pinlou, \emph{2-distance coloring of sparse graphs}, J. Graph Theory {\bf 77(3)} (2014), 190--218.

\end{thebibliography}


\vfill
\end{document}