%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,hyperref} 
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Bounding the Obstructions for Apices of Minor-closed Graph Classes}
%

% 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{Névole, B.}\index{Nonyme, A.}
%

% Citer un par un les auteurs et leur affiliation
Ignasi Sau, LIRMM, Univ Montpellier, CNRS, Montpellier, France,\\ {\tt ignasi.sau@lirmm.fr}\\
\indent
\underline{Giannos Stamoulis}, LIRMM, Univ Montpellier, Montpellier, France,\\ {\tt giannos.stamoulis@lirmm.fr}\\ %souligner l'orateur
\indent
Dimitrios M. Thilikos, LIRMM, Univ Montpellier, CNRS, Montpellier, France, {\tt sedthilk@thilikos.info}\\
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le résumé

A graph class ${\cal G}$ is
{\em minor-closed} if every minor
%\footnote{A graph $H$ is a {\em minor} of $G$ if a graph isomorphic to $H$
%can be obtained from some subgraph of $G$ after applying edge contractions. As in this paper we consider only simple graphs, we insist
%that in case multiple edges are created after a contraction, then these edges are automatically suppressed to simple edges.}
of a graph in ${\cal G}$
is also a member of ${\cal G}.$
Given
a graph class ${\cal G}$, its {\em minor obstruction set}, denoted by ${\bf obs}({\cal G})$, is defined as the set of all minor-minimal graphs not in ${\cal G}$.
According to the celebrated Robertson and Seymour’s theorem~\cite{RobertsonSXX}, the obstruction set of every minor-closed graph class is finite.

The study of ${\bf obs}({\cal G})$ for distinct instantiations of minor-closed graph classes ${\cal G}$ is an active topic in graph theory.
There are many results in the literature that achieve a complete or partial identification of the obstruction set of different minor-closed graph classes.


Let ${\cal G}$ be a minor-closed graph class
and $k$ be a non-negative integer. %\ig{why not assuming since the beginning that ${\cal G}$ is minor-closed?}.
We say that a graph $G$ is a {\em $k$-apex} of ${\cal G}$ if  $G$ contains a  et $S$ of at most $k$ vertices such that  $G\setminus S$ belongs to ${\cal G}.$ We denote by ${\cal A}_k ({\cal G})$ the set of all graphs that are $k$-apices of ${\cal G}$
and note that if ${\cal G}$ is minor-closed, then also ${\cal A}_k ({\cal G})$ is minor-closed.
We prove that every graph in the obstruction set of ${\cal A}_k ({\cal G})$ has size at most $2^{2^{2^{2^{{\sf poly}(k)}}}},$ where ${\sf poly}$ is a polynomial function whose degree depends on the maximum size of a graph in ${\bf obs}({\cal G}).$
This bound drops to $2^{2^{{\sf poly}(k)}}$ when ${\cal G}$ excludes some apex graph as a minor, i.e., a graph that is an $1$-apex to the class of planar graphs.
\smallskip

%Si vous souhaitez ajouter une figure, faites-en sorte qu'elle soit
%compilable par {\tt pdflatex} (pas de {\tt pstricks} ou d'{\tt eps}). Vous pouvez aussi
%utiliser tikz si vous le souhaitez.
%
%\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{RobertsonSXX}
Neil Robertson and Paul~D. Seymour.
\newblock {Graph Minors. {XX}. Wagner's conjecture}.
\newblock {\em Journal of Combinatorial Theory, Series B}, 92(2):325--357,
  2004.
\newblock \href {https://doi.org/10.1016/j.jctb.2004.08.001}
  {\path{doi:10.1016/j.jctb.2004.08.001}}.
\end{thebibliography}


\vfill
\end{document}
