%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*{N. Bousquet, L. Feuilloley et T. Pierron : Certification locale et (petits) mineurs interdits}
%

% Pour le sommaire
\addcontentsline{toc}{section}{N. Bousquet, L. Feuilloley et T. Pierron : Certification locale et (petits) mineurs interdits}
%

% Pour la liste des auteurs
\index{Bousquet, N.}\index{Feuilloley, L.}\index{Pierron, T.}
%

% Citer un par un les auteurs et leur affiliation
Nicolas Bousquet, Université Lyon 1, LIRIS.\\ \indent{\tt nicolas.bousquet@univ-lyon1.fr}\\
\indent
\underline{Laurent Feuilloley}, Université Lyon 1, LIRIS.\\ 
\indent{\tt laurent.feuilloley@univ-lyon1.fr}\\
\indent
Théo Pierron, Université Lyon 1, LIRIS.\\ 
\indent{\tt theo.pierron@univ-lyon1.fr}\\
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

La certification locale consiste à étiqueter les sommets d'un graphe, pour certifier une propriété. Les sommets du graphe peuvent vérifier collectivement que la certification est correcte, en prenant connaissance des étiquettes de leur voisins. 

Il est connu depuis longtemps que l'on peut certifier l'acyclicité avec des étiquettes de $\Theta(\log n)$ bits par sommet (où $n$ est la taille du graphe). Plus récemment, il a été montré que l'on pouvait certifier la planarité (et le fait d'avoir un genre borné) avec des étiquettes de même taille. 
Se pose alors une question naturelle: peut-on certifier n'importe quelle classe définie par des mineurs interdits avec des étiquettes de taille $\Theta(\log n)$?

Nous montrons que c'est le cas pour les petits mineurs (typiquement ceux sur 4 sommets)~\cite{m}. Un outil essentiel dans nos preuves est la certification de la 2- et 3-connectivité.


\begin{thebibliography}{9}

\bibitem{m}
N. Bousquet, L. Feuilloley and Th{\'{e}}o Pierron, \emph{Local certification of graph decompositions and applications to minor-free
classes}, arxiv: 2108.00059.

\end{thebibliography}


\vfill
\end{document}
