---------------------------------------------------------------------- Titre : graphes arbitrairement décomposables Directeurs : O. Baudon, C Gavoille Equipe : Algorithmique et Combinatoire Thème : Graphes et applications Candidat potentiel : Frédéric Gilbert Résumé : Soit lambda une décomposition d'un entier n en k entiers n1, ... nk (ie n1 + ... + nk = n). Un graphe G = (V,E) à n sommets est dit lambda-décomposable ssi il existe une partition de V = (V1,...Vk) telle que pour tout i, |Vi| = ni et le sous-graphe induit par Vi est connexe. Un graphe G à n sommets est dit arbitrairement décomposable ssi pour toute décomposition lambda de n, G est lambda-décomposable. Ce problème a été récemment étudié par plusieurs auteurs, et principalement dans le cas des arbres. Par exemple, le problème suivant : "Soit lambda une décomposition de n et T un arbre de degré maximum 3 et d'ordre n. T est-il lambda-décomposable ?" est NP-complet. D'autre part, savoir si un graphe est arbitrairement décomposable est intermédiaire entre l'existence d'un couplage parfait et celle d'une chaîne hamiltonienne (traçabilité). On se propose d'étudier les questions suivantes : - cas des graphes k-connexes, en particulier quand k = 2,3 - relation entre la connectivité et la décomposition arbitraire, - relaxation de conditions de traçabilité conservant la décomposabilité arbitraire, par exemple sur les graphes claw-free. - étude de classes intermédiaires entre graphes arbitrairement décomposables et graphes traçables : graphes on-line décomposables, graphes récursivement décomposables - étude d'une sous-classe des graphes claw-free : les graphes fortement récursivement décomposables. Ces études seront faites à la fois d'un point de vue structurel et algorithmique. Références principales : [1] O. Baudon D. Barth and J. Puech. Networks sharing : a polynomial algorithm for tripodes. Discrete Applied Mathematics, 119 :205\u2013216, 2002. [2] D. Barth and H. Fournier. A degree bound on decomposable trees. Discrete Applied Mathematics, 306 :469\u2013477, 2006. [4] Tuza Hornak and M. Wozniak. On-line arbitrarily vertex decomposable trees. Discrete Applied Mathematics, 155 :1420\u20131429, 2007. [8] A. Marczyk. An Ore-type condition for arbitrarily vertex decomposable graphs. Electronic Notes in Discrete Mathematics 22 :477-480, 2005. -------------------------------------------------------------------------