Théorie des graphes extrémaux

Soit ${\displaystyle P}$ une propriété sur les graphes qui se conserve par ajout d'arêtes et ${\displaystyle G=(V,E)}$ un graphe quelconque. ${\displaystyle G}$ est dit extrémal par rapport à la propriété P si :

• ${\displaystyle G}$ ne vérifie pas ${\displaystyle P}$ ;
• ${\displaystyle \forall (x,y)}$ non adjacents dans ${\displaystyle G}$, le graphe ${\displaystyle G'=(V,E\cup (x,y))}$ vérifie ${\displaystyle P}$.

D'autre part, une fonction ${\displaystyle f}$ est une borne inférieure par rapport à la propriété ${\displaystyle P}$ si ${\displaystyle \forall G=(V,E),|E|>f(|V|)}$ permet d'assurer que ${\displaystyle G}$ vérifie ${\displaystyle P}$.

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

Pour la propriété ${\displaystyle P=}$ "ne pas admettre de triangles comme sous-graphe", une borne inférieure est ${\displaystyle |E|={\frac {|V|^{2}}{4}}}$. Les graphes extrémaux sont exactement les graphes bipartis ${\displaystyle K_{k,k}}$ et ${\displaystyle K_{k,k+1}}$.

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

• Théorème d'Erdős-Stone

• (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.

• Portail de l'informatique théorique
• Portail des mathématiques