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

%%%%%%%% Champs titre %%%%%%%
% Pour le titre
\subsection*{Décompositions arborescentes avec \emph{independence\\ number} borné}
%

% Pour le sommaire
\addcontentsline{toc}{section}{C.\ Dallard, M.\ Milani\v{c} et K.\ \v{S}torgel : Décompositions arborescentes avec independence number borné}
%

% Pour la liste des auteurs
\index{Dallard, C.}\index{Milani\v{c}, M.}\index{\v{S}torgel, K.}
%

% Citer un par un les auteurs et leur affiliation
\indent \underline{Clément Dallard}, FAMNIT \& IAM, University of Primorska, Koper, Slovenia {\tt clement.dallard@famnit.upr.si}\\
\indent Martin Milani\v{c}, FAMNIT \& IAM, University of Primorska, Koper, Slovenia {\tt martin.milanic@upr.si}\\
\indent Kenny \v{S}torgel, FIS, Novo mesto, Slovenia, et FAMNIT, University of Primorska, Koper, Slovenia {\tt kennystorgel.research@gmail.com}\\
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

L'\emph{independence number} d'une décomposition arborescente $\mathcal T$ d'un graphe est le plus petit entier $k$ tel que chaque sac de $\mathcal T$ induit un sous-graphe dans lequel tout ensemble indépendant est de taille au plus $k$.
% Le \emph{tree-independence number} d'un graphe $G$ est le plus petit entier $k$ tel que $G$ a une décomposition arborescente avec independence number au plus $k$.
Quand un graphe est donné avec une décomposition arborescente dont l'independence number est borné, le problème \textsc{Maximum Weight Independent Set} (MWIS) peut être résolu en temps polynomial.

Nous considérons six relations de graphes (les relations de sous-graphe, mineur topologique et mineur, ainsi que leurs variantes induites) et pour chacune d'entre elles caractérisons les graphes $H$ tels que tout graphe excluant $H$ suivant cette relation admet une décomposition arborescente dont l'independence number est borné.
De plus, nous montrons comment obtenir une telle décomposition arborescente efficacement.
Il en découle que MWIS peut être résolu en temps polynomial dans les classes de graphes excluant $W_4$, $K_5^-$ ou $K_{2,q}$ pour $q \geq 2$ comme mineur induit.
% Notons que la classe des graphes excluant $K_{2,q}$ pour $q \geq 3$ généralise strictement la classe des graphes cordaux.
Plus généralement, nos résultats impliquent que le problème \textsc{Maximum Weight Independent $\mathcal H$-Packing}, qui généralise notamment MWIS et \textsc{Maximum Weight Induced Matching}, est résoluble en temps polynomial dans ces mêmes classes de graphes.

\bigskip 

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}[scale=1.1]
    \usetikzlibrary{calc}
    \tikzstyle{every path}=[very thick]
    \tikzset{every node/.style={draw,circle,fill=black,inner sep=0pt,minimum size=7.5pt}}

    \begin{scope}
        \node (a) at ($(0,0) + (0:1)$) {};
        \node (b) at ($(0,0) + (90:1)$) {};
        \node (c) at ($(0,0) + (180:1)$) {};
        \node (d) at ($(0,0) + (270:1)$) {};
        \node (w) at (0,0) {};

        \draw (a) to (b)
              (b) to (c)
              (c) to (d)
              (d) to (a)
              (w) to (a)
              (w) to (b)
              (w) to (c)
              (w) to (d);

        % \node[draw=none, fill=none] at (0,-1.5) {$\mathstrut W_4$};
    \end{scope}
    \begin{scope}[xshift=3.5cm]
        \def\r{18};
        \node (a) at ($(0,0) + (0+\r:1)$) {};
        \node (b) at ($(0,0) + (72+\r:1)$) {};
        \node (c) at ($(0,0) + (144+\r:1)$) {};
        \node (d) at ($(0,0) + (216+\r:1)$) {};
        \node (e) at ($(0,0) + (288+\r:1)$) {};

        \draw (a) to (b)
              (a) to (d)
              (a) to (e)
              (b) to (c)
              (b) to (d)
              (b) to (e)
              (c) to (d)
              (c) to (e)
              (d) to (e);

        % \node[draw=none, fill=none] at (0,-1.5) {$\mathstrut K_5^-$};
    \end{scope}
    \begin{scope}[xshift=7cm]
        \node (a) at (-1,0) {};
        \node (b) at (1,0) {};
        \node (q1) at (0,1) {};
        \node (q2) at (0,0.5) {};
        \node (qm) at (0,0) {};
        \node (qnm1) at (0,-0.5) {};
        \node (qn) at (0,-1) {};

        \draw (a) to (q1)
              (a) to (q2)
              (a) to (qm)
              (a) to (qnm1)
              (a) to (qn)
              (b) to (q1)
              (b) to (q2)
              (b) to (qm)
              (b) to (qnm1)
              (b) to (qn);

        % \node[draw=none, fill=none] at (0,-1.5) {$\mathstrut K_{2,5}$};
    \end{scope}
    \end{tikzpicture}
    \caption{De la gauche vers la droite, les graphes $W_4$, $K_5^-$ et $K_{2,5}$.}
    \label{figure induced minors}
\end{figure}

\vfill
\end{document}
