- Théorie des graphes extrémaux
-
En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété P est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété P. 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
Soit P une propriété sur les graphes qui se conserve par ajout d'arêtes et G = (V,E) un graphe quelconque. G est dit extrémal par rapport à la propriété P si :
- G ne vérifie pas P ;
non adjacents dans G, le graphe 
vérifie P.
D'autre part, une fonction f est une borne inférieure par rapport à la propriété P si
permet d'assurer que G vérifie P.À noter que les graphes extrémaux ne vérifient pas nécessairement la meilleure borne inférieure.
Exemples
Pour la propriété P = "ne pas admettre de triangles comme sous-graphe", une borne inférieure est
. Les graphes extrémaux sont exactement les graphes bipartis Kk,k et Kk,k + 1.Plus généralement, pour Pl = "ne pas admettre de clique de taille l comme sous-graphe", les graphes extrémaux sont les graphes complets (l-1)-partis Kk,..,k,k + 1,..,k + 1. Ce résultat est une conséquence du théorème de Turán (en), qui fournit également une borne inférieure (trop longue pour être incluse ici).
Références
- (en) J. H. van Lint et R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001, 2e éd. (ISBN 0-521-80340-3), particulièrement le chapitre 4 : « Turan's theorem and extremal graphs »
- (en) Reinhard Diestel (de), Graph Theory, Springer-Verlag, Heidelberg, New York, 1997, 2000, 2005. Version électronique de la 3e édition disponible en ligne gratuitement : [1]
Wikimedia Foundation. 2010.
