%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{hyperref}
\begin{document}
\newpage

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{J. Bensmail et F. Fioravantes et F. Mc Inerney et N. Nisse  : Le Jeu du Plus Grand Sous-Graphe Connexe}
%

% Pour le sommaire
\addcontentsline{toc}{section}{J. Bensmail et F. Fioravantes et F. Mc Inerney et N. Nisse  : Le Jeu du Plus Grand Sous-Graphe Connexe}
%

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

% Citer un par un les auteurs et leur affiliation
Julien Bensmail, Universit\'e C\^ote d'Azur, Inria, CNRS, I3S, Valbonne, France, julien.bensmail@inria.fr

\indent
\underline{Foivos Fioravantes}, Universit\'e C\^ote d'Azur, Inria, CNRS, I3S, Valbonne, France, foivos.fioravantes@inria.fr

\indent
Fionn Mc Inerney, CISPA Helmholtz Center for Information Security, Saarbr\"{u}cken, Germany, fmcinern@gmail.com

\indent
Nicolas Nisse, Universit\'e C\^ote d'Azur, Inria, CNRS, I3S, Valbonne, France, nicolas.nisse@inria.fr
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%



Nous d\'efinissons le jeu du plus grand sous-graphe connexe.
Ce jeu se joue sur un graphe dont les sommets sont initialement non colorés. Lors de tours successifs, le premier joueur, Alice, colore en rouge un sommet non coloré, puis le second joueur, Bob, colore un sommet non coloré en bleu. Le jeu s'achève lorsque tous les sommets du graphe ont été colorés. Le vainqueur est le joueur dont le sous-graphe coloré a la plus grande composante connexe.

Nous prouvons que, si Alice joue optimalement, Bob ne peut jamais gagner, % lors d'une partie de ce jeu,
et définissons une classe de graphes infinie, appelés {\it graphes miroirs}, dans lesquels Bob peut forcer une égalité. Du point de vue complexité, nous montrons ensuite que déterminer l'issue du jeu est PSPACE-complet même lorsque restreint aux graphes bipartis de petit diamètre, et que reconnaître un graphe miroir est GI-difficile. Enfin, nous caractérisons les chemins et cycles pour lesquels Alice a une stratégie gagnante, et nous prouvons que l’issue du jeu peut être déterminée en temps linéaire dans la classe des cographes. 
 
 Une version de ce travail a été présentée lors de WG 2021~\cite{BFMN21}. La version complète se trouve \href{https://hal.inria.fr/hal-03137305/file/The_Largest_Connected_Subgraph_Game.pdf}{ici}.


\begin{thebibliography}{99}

\bibitem{BFMN21}
J.~Bensmail and F.~Fioravantes and F.~Mc~Inerney and N.~Nisse, (2021) \emph{The Largest Connected Subgraph Game}. In$:$ Graph-Theoretic Concepts in Computer Science. WG 2021. Lecture Notes in Computer Science, vol 12911. Springer, Cham.
\end{thebibliography}


\vfill
\end{document}
