Accueil🇫🇷Chercher

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é

Théorème d'Erdős–Pósa[1] Il existe une fonction f: NN telle que pour tout graphe G et tout entier positif k, l'un des énoncés suivant soit vrai :

  • G contient 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

Ce 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) ≥ 1/8 k log k.

Propriété d'Erdős-Pósa

Par 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: NN 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 a 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 a 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

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, 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

  1. 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)
  2. Un graphe est une forêt s'il est acyclique, autrement dit si c'est un arbre ou une union d'arbres disjoints.
  3. László Lovász, « On graphs not containing independent circuits », Mat. Lapok, vol. 16, , p. 289–299
  4. 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)
  5. 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)
  6. 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)
  7. 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 Accès libre)
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.