Théorème d'Erdős-Pósa
En théorie des graphes, le théorème d'Erdős-Pósa, nommé après Paul Erdős et Lajos Pósa (en), 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é
modifierThéorème d'Erdős–Pósa[1] — Il existe une fonction f : N → N telle que pour tout graphe G et tout entier positif k, l'un des énoncés suivants soit vrai :
- G contient au moins k cycles sommet-disjoints ; ou
- G a un ensemble X de sommets, de taille au plus f(k), tel que G − X est une forêt[2].
De plus, f(k) = O(k log k).
Estimation de la fonction f
modifierCe théorème généralise un résultat non publié de Béla Bollobás selon lequel f(2) = 3. Lovász a donné une description complète des graphes ne contenant pas 2 cycles disjoints[3]. Voss a prouvé[4] que f(3) = 6 et 9 ≤ f(4) ≤ 12. Pour un k général, Erdős et Pósa ont montré[1] que toute fonction f satisfaisant l'énoncé du théorème ci-dessus est telle que f(k) = Ω(k log k). Voss a également obtenu[4] la majoration f(k) = (2 + o(1)) k log k et la minoration f(k) ≥ 18 k log k.
Propriété d'Erdős-Pósa
modifierPar analogie avec le théorème, on dit qu'une famille F de graphes a la propriété d'Erdős–Pósa s'il existe une fonction f: N → N telle que pour tout graphe G et tout entier positif k, l'un des énoncés suivants est vrai :
- G contient k sous-graphes sommet-disjoints, chacun isomorphe à un graphe de F ; ou
- G a un ensemble X de sommets, de taille au plus f(k), tel que G − X n'a pas de sous-graphe isomorphe à un graphe de F.
La (plus petite) fonction f dans la définition ci-dessus est appelée borne pour la propriété d'Erdős–Pósa de la famille F. Avec cette terminologie, le théorème d'Erdős–Pósa se reformule comme suit : la famille F de tous les cycles a la propriété d'Erdős et Pósa, avec borne f(k) = Θ(k log k). Étant donné un graphe H, notons F(H) la classe de tous les graphes qui contiennent H 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 :
Théorème[5] — F(H) a la propriété d' Erdős–Pósa si et seulement si H est un graphe planaire.
Il a ensuite été démontré que la borne correspondante est f(k) = Θ(k) si H est une forêt[6] et qu'elle est f(k) = Θ(k log k) pour tout autre graphe H planaire[7]. Le cas particulier où H est un triangle est équivalent au théorème d'Erdős et Pósa.
Relation à d'autres théorèmes
modifierOn 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, F(K2) a la propriété d'Erdős-Pósa avec borne f(k) = k. 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
modifier- Paul Erdős et Lajos Pósa, « On independent circuits contained in a graph », Canad. Journ. Math, vol. 17, , p. 347–352 (DOI 10.4153/CJM-1965-035-8)
- Un graphe est une forêt s'il est acyclique, autrement dit si c'est un arbre ou une union d'arbres disjoints.
- László Lovász, « On graphs not containing independent circuits », Mat. Lapok, vol. 16, , p. 289–299
- Heinz-Jürgen Voss, « Eigenschaften von Graphen, die keine k+1 knotenfremde Kreise enthalten », Mathematische Nachrichten, vol. 40, , p. 19–25 (DOI 10.1002/mana.19690400104)
- Neil Robertson et Paul Seymour, « Graph minors. V. Excluding a planar graph », Journal of Combinatorial Theory, Series B, vol. 41, , p. 92–114 (DOI 10.1016/0095-8956(86)90030-4)
- Samuel Fiorini, Gwenaël Joret et David R. Wood, « Excluded Forest Minors and the Erdős–Pósa Property », Combinatorics, Probability and Computing, vol. 22, no 5, , p. 700–721 (DOI 10.1017/S0963548313000266, arXiv 1204.5192, S2CID 122708)
-
Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret et Jean-Florent Raymond, « A tight Erdős-Pósa function for planar minors », Advances in Combinatorics, vol. 2, , p. 33pp (DOI 10.19086/aic.10807
)
