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

Stanley propose en 1981 un nouveau problčme de reconstruction pour les graphes non-orientés. Switcher en un sommet consiste ŕ remplacer toutes les arętes incidentes ŕ ce sommet par des non-arętes et vice-versa. Dans la premičre partie nous présenterons de nouveaux problčmes de reconstruction qui s'inspirent de, et généralisent, celui de Stanley, ainsi qu'une méthode qui permet d'établir des résultats similaires ŕ ceux obtenus par Stanley, Ellingham et Royle, et Krasikov et Roditty dans le cas du problčme de Stanley, en particulier un Lemme "ŕ la Kelly". Dans la seconde partie nous présentons la conjecture de Hahn et Jackson, qui s'insčre dans le cadre de l'étude des relations entre stables et chemins dans les graphes orientés. 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.