Théorie des graphes extrémaux

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété . L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits.

L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes.

Définition rigoureuse[modifier | modifier le code]

Soit une propriété sur les graphes qui se conserve par ajout d'arêtes et un graphe quelconque. est dit extrémal par rapport à la propriété P si :

  • ne vérifie pas  ;
  • non adjacents dans , le graphe vérifie .

D'autre part, une fonction est une borne inférieure par rapport à la propriété si permet d'assurer que vérifie .

À noter que les graphes extrémaux ne vérifient pas nécessairement la meilleure borne inférieure.

Exemples[modifier | modifier le code]

Pour la propriété "ne pas admettre de triangles comme sous-graphe", une borne inférieure est . Les graphes extrémaux sont exactement les graphes bipartis et .

Plus généralement, pour "ne pas admettre de clique de taille l comme sous-graphe", les graphes extrémaux sont les graphes complets (l-1)-partis . Ce résultat est une conséquence du théorème de Turán, qui fournit également une borne inférieure (trop longue pour être incluse ici).

Références[modifier | modifier le code]