%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*{J. Bang-Jensen, S. Bessy, D. Gonçalves et L. Picasarri-Arrieta : Complexité de quelques problèmes de partition d'arcs dans les graphes dirigés}

% Pour le sommaire
\addcontentsline{toc}{section}{J. Bang-Jensen, S. Bessy, D. Gonçalves et L. Picasarri-Arrieta : Complexité de quelques problèmes de partition d'arcs dans les graphes dirigés}
%

% Pour la liste des auteurs
\index{Bang-Jensen, J.}\index{Bessy, S.}\index{Gonçalves, D.}\index{Picasarri-Arrieta, L.}
%

% Citer un par un les auteurs et leur affiliation
Jørgen Bang-Jensen, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark, {\tt jbj@imada.sdu.dk}\\
\indent
Stéphane Bessy, LIRMM, Montpellier, {\tt stephane.bessy@lirmm.fr}\\
\indent
Daniel Gonçalves, LIRMM, Montpellier, {\tt daniel.goncalves@lirmm.fr}\\
\indent
\underline{Lucas Picasarri-Arrieta}, INRIA, Sophia-Antipolis, \\{\tt lucas.picasarri-arrieta@inria.fr}\\ 
\\
%%%%%% Fin Champs titre %%%%%%%%%%%%%%

Nous étudions ici la complexité de décider si un graphe dirigé $D=(V,A)$ admet une partition $(A_1,A_2)$ de ses arcs, de sorte que chacun des deux graphes $(V,A_1)$ et $(V,A_2)$ vérifie une propriété particulière. On s'intéresse principalement aux propriétés suivantes : être connexe, être fortement connexe, être acyclique (couvrant ou non), contenir une arborescence entrante (ou sortante), avoir une condition sur le degré entrant (ou sortant), contenir un certain nombre d'arcs, être eulérien ou être un cycle. Au total, nous fixons, ou redonnons, la complexité de 120 problèmes de partition d'arcs sur les graphes dirigés.  Pour certaines paires de propriétés, nous donnons également des conditions de connexité qui garantissent l'existence d'une telle partition.

\smallskip
Le sujet est directement lié à deux célèbres conjectures (\cite{thom}, \cite{bj-yeo}). La première, proposée par C. Thomassen en 1989, est la suivante :  il existe un entier $k$ tel que tout graphe dirigé $k$-arc-fort admet une arborescence sortante et une arborescence entrante arc-disjointes. En 2004, J. Bang-Jensen et A. Yeo proposèrent une conjecture plus forte : il existe un entier $k$ tel que tout graphe dirigé $k$-arc-fort admet deux sous-graphes fortement connexes couvrants arc-disjoints.
\smallskip



\begin{thebibliography}{99}

\bibitem{thom}
C. Thomassen, \emph{Configurations in graphs of large minimum degree, connectivity, or
chromatic number}, In Proceedings of the third international conference on Combinatorial mathematics, pages 402-412, 1989.

\bibitem{bj-yeo}
J. Bang-Jensen and A. Yeo, \emph{Decomposing $k$-arc-strong tournaments into strong spanning subdigraphs}, Combinatorica, 24(5):331--349, 2004.

\end{thebibliography}
\vfill
\end{document}