| Résumé | Robertson et Seymour ont récemment donné (dans "Graph Minors 16, 2003") une caractérisation des graphes ne contenant pas un graphe arbitraire H comme mineur. Cette caractérisation est basée sur une décomposition arborescente très complexe des graphes. Basé sur cette dernière, nous montrons que les graphes excluant un mineur sont "k-chemins séparables" où k est une constante ne dépendant que du mineur exclu. Grosso modo cela signifie que de tels graphes peuvent être coupé en deux en supprimant au plus k plus courts chemins. La propriété de k-chemin séparable a de nombreuses applications: routage, oracle de distance, petits-monde, etc.
Dans cette exposé je me contenterai de donner les concepts de base pour comprendre l'énoncé du théorème de décomposition de Robertson et Seymour, ainsi que les idées principales permettant de montrer que les graphes excluant un mineur sont k-chemins séparables.
Mots-clés: décomposition arborescente, surface orientable, surface non-orientable, vortex, joint, torso, etc. |