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$ ;
$\forall (x,y)$ non adjacents dans $G$ , le graphe $G'=(V,E\cup (x,y))$ vérifie $P$ .

D'autre part, une fonction $f$ est une borne inférieure par rapport à la propriété $P$ si $\forall G=(V,E),|E|>f(|V|)$ 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 $|E|={\frac {|V|^{2}}{4}}$ . Les graphes extrémaux sont exactement les graphes bipartis $K_{k,k}$ et $K_{k,k+1}$ .

Plus généralement, pour $P_{l}=$ "ne pas admettre de clique de taille l comme sous-graphe", les graphes extrémaux sont les graphes complets (l-1)-partis $K_{k,..,k,k+1,..,k+1}$ . 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

(en) J. H. van Lint et R. M. Wilson, A Course in Combinatorics, Cambridge University Press, 2001, 2^e éd. (ISBN 0-521-80340-3), particulièrement le chapitre 4 : « Turan's theorem and extremal graphs »
(en) Reinhard Diestel, Graph Theory, Springer-Verlag, Heidelberg, New York, 1997, 2000, 2005 [lire en ligne] la 3^e éd.