Reconstruction Dans Les Graphes Orient s Et Color s Et Autres Probl mes

Stanley propose en 1981 un nouveau problme de reconstruction pour les graphes non-orients. Switcher en un sommet consiste remplacer toutes les artes incidentes ce sommet par des non-artes et vice-versa. Dans la premire partie nous prsenterons de nouveaux problmes de reconstruction qui s'inspirent de, et gnralisent, celui de Stanley, ainsi qu'une mthode qui permet d'tablir des rsultats similaires ceux obtenus par Stanley, Ellingham et Royle, et Krasikov et Roditty dans le cas du problme de Stanley, en particulier un Lemme " la Kelly". Dans la seconde partie nous prsentons la conjecture de Hahn et Jackson, qui s'insre dans le cadre de l'tude des relations entre stables et chemins dans les graphes orients. Hahn et Jackson conjecturent que pour tout entier naturel k, il existe un graphe de stabilit k tel que quelques soient les k-1 chemins que l'on supprime (avec leurs sommets) du graphe, la cardinalit du graphe obtenu reste k. Cette conjecture est aussi forte que possible. Nous construisons explicitement une famille infinie de tels graphes, pour tout k de la forme 2^n.3^m, o n et m sont deux entiers naturels.