vignette|Deux cycles disjoints (ABCF et GHIJ en rouge) et un coupe-cycles {A, C, G}. En théorie des graphes, le théorème d'Erdős-Pósa, nommé après Paul Erdős et , relie dans un graphe la taille maximale d'une collection de cycles disjoints à la taille minimale d'un coupe-cycles de sommets (feedback vertex set).
Énoncé
Estimation de la fonction Ce théorème généralise un résultat non publié de Béla Bollobás selon lequel . Lovász a donné une description complète des graphes ne contenant pas 2 cycles disjoints. Voss a prouvé que et . Pour un général, Erdős et Pósa ont montré que toute fonction f satisfaisant l'énoncé du théorème ci-dessus est telle que . Voss a également obtenu la majoration et la minoration .
Propriété d'Erdős-Pósa Par analogie avec le théorème, on dit qu'une famille de graphes a la propriété d'Erdős–Pósa s'il existe une fonction telle que pour tout graphe et tout entier positif , l'un des énoncés suivants est vrai :
contient sous-graphes sommet-disjoints, chacun isomorphe à un graphe de ; ou a un ensemble de sommets, de taille au plus , tel que n'a pas de sous-graphe isomorphe à un graphe de .
La (plus petite) fonction dans la définition ci-dessus est appelée borne pour la propriété d'Erdős–Pósa de la famille . Avec cette terminologie, le théorème d'Erdős–Pósa se reformule comme suit : la famille de tous les cycles a la propriété d'Erdős et Pósa, avec borne . Étant donné un graphe , notons () la classe de tous les graphes qui contiennent comme mineur. En corollaire du théorème d'exclusion de grille, Robertson et Seymour ont démontré une généralisation considérable du théorème d'Erdős et Pósa :
Il a ensuite été démontré que la borne correspondante est si est une forêt et qu'elle est pour tout autre graphe planaire. Le cas particulier où est un triangle est équivalent au théorème d'Erdős et Pósa.
Relation à d'autres théorèmes On peut voir le théorème d'Erdős–Pósa comme un cousin du théorème de Kőnig qui, exprimé dans le formalisme décrit ci-dessus, revient à dire que dans les graphes bipartis, a la propriété d'Erdős-Pósa avec borne . Il en est de même pour le théorème de Menger, qui lui aussi relie un nombre maximum d'objets disjoints dans un graphe (dans ce cas des chemins) au nombre minimum de sommets à retirer pour détruire tous ces objets (un séparateur).
Notes et références
Catégorie:Théorie des graphes Erdos-Posa