%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}
\usepackage{ dsfont }
\usepackage{amsfonts}

\newtheorem{resultat}{Théorème}

\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{J. Bensmail, F. Fioravantes, F. Mc~Inerney, N. Nisse, N.Oijid : Jeu du plus grand sous-graphe connexe : Maker-Breaker}
%

% Pour le sommaire
\addcontentsline{toc}{section}{J. Bensmail, F. Fioravantes, F. Mc~Inerney, N. Nisse, N.Oijid : Jeu du plus grand sous-graphe connexe : Maker-Breaker}
%

% Pour la liste des auteurs
\index{Bensmail, J.}
\index{Fioravantes, F.}
\index{MC~Inerney, F.}
\index{Nisse, N.}
\index{Oijid, N.}

%

% Citer un par un les auteurs et leur affiliation
Julien Bensmail, U. C\^ote d'Azur, CNRS, Inria, I3S, France, {\tt julien.bensmail@inria.fr}\\
\indent
Foivos Fioravantes, U. C\^ote d'Azur, CNRS, Inria, I3S, France, {\tt ffioravantes@gmail.com} \\
\indent
Fionn Mc~Inerney, CISPA Helmholtz Center for Information Security, Saarbr\"{u}cken, Germany, {\tt fmcinern@gmail.com} \\
\indent
Nicolas Nisse, U. C\^ote d'Azur, CNRS, Inria, I3S, France, {\tt nicolas.nisse@inria.fr}\\
\indent
\underline{Nacim Oijid},  LIRIS, U. Lyon 1, {\tt nacim.oijid@univ-lyon1.fr}\\%souligner l'orateur


%%%%%% Fin Champs titre %%%%%%%%%%%%%%

% Ensuite, le rÃ©sumÃ©
\'Etant donnés un graphe $G$ et un entier $k \in \mathbb{N}$, on introduit le jeu Maker-Breaker suivant sur $G$. \`A chaque tour, Alice colorie un sommet non colorié de $G$ en rouge, puis Bob en colorie un en bleu (s'il en reste). Une fois que tous les sommets ont été coloriés, Alice gagne s'il existe une  composante connexe rouge d'ordre au moins $k$, sinon Bob gagne. Ce jeu est une version Maker-Breaker du jeu du plus grand sous-graphe connexe introduit dans \cite{LCSG-MM}. On s'intéresse ici au calcul de $c_g(G)$, qui est le plus grand entier $k$ tel qu'Alice gagne en jouant sur $G$, peu importe la stratégie adoptée par Bob.

\'Etant donnés un graphe $G$ et un entier $k \ge 1$, on montre que décider si $c_g(G) \ge k$ est {\sc Pspace}-complet, même si on contraint $G$ à être dans la classe des graphes bipartis de diamètre au plus $4$, dans la classe des graphes scindés ou encore des graphes planaires. On s'intéresse ensuite aux graphes {\it A-parfaits}, c'est-à-dire, ceux qui vérifient $c_g(G) = \left \lceil \frac{|V(G)|}{2}\right \rceil$, soit la plus grande valeur possible. On montre qu'il existe des graphes arbitrairement grands et $d$-réguliers qui sont A-parfaits pour tout $d \ge 4$, mais qu'aucun graphe cubique ayant plus de 133 sommets n'est $A$-parfait. De plus, on donne des conditions suffisantes en termes de nombre d'arêtes ou de degré minimum et maximum d'un graphe afin qu'il soit A-parfait.

Enfin, on montre que $c_g(G)$ peut être calculé en temps polynomial sur certaines classes de graphes et on conclut avec quelques questions toujours ouvertes. 


\begin{thebibliography}{99}

\bibitem{LCSG-MM}
 {J. Bensmail and F. Fioravantes and F. Mc~Inerney and N. Nisse},
 \emph{The Largest Connected Subgraph Game},
 \textit{Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science ({WG} 2021)},
 \textbf{Lecture Notes in Computer Science},
 {Springer},
 {2021} 

\end{thebibliography}


\vfill
\end{document}