Graphe de Turán
# Graphe de Turán

En théorie des graphes, un graphe de Turán (noté $T(n,r)$), aussi appelé maximally saturated graph, est un élément d'une famille de graphes qui portent le nom de Pál Turán.

Le graphe $T(n,r)$ possède $n$ sommets, partitionnés en $r$ sous-ensembles les plus équilibrés possibles, et chaque sommet est relié à tous les sommets qui ne sont pas dans son sous-ensemble. Par équilibré, on entend que le graphe a $(n{\text{ mod }}r)$ sous-ensembles de taille $\lceil n/r\rceil$, et $r-(n{\text{ mod }}r)$ sous-ensembles de taille $\lfloor n/r\rfloor$.

## Définition

La graphe the Turán de paramètres n et r, noté $T(n,r)$ possède $n$ sommets, partitionnés en $r$ sous-ensembles les plus équilibrés possibles, et chaque sommet est relié à tous les sommets qui ne sont pas dans son sous-ensemble. Par équilibré, on entend que le graphe aura $(n{\text{ mod }}r)$ sous-ensembles de taille $\lceil n/r\rceil$, et $r-(n{\text{ mod }}r)$ sous-ensembles de taille $\lfloor n/r\rfloor$.

## Propriétés

Le nombre chromatique du graphe $T(n,r)$ est r.

## Cas particuliers et inclusions

Les graphes bipartis complets sont des graphes de Turán.

Ce sont des cographes, c'est-à-dire qu'ils peuvent être formés par des unions disjointes et des passages au graphe complémentaire. On peut le réaliser de la manière suivante :

pour chaque stable du graphe final,

* faire d'abord une union de tous les sommets,
* passer au complémentaire (dans chaque ensemble) pour avoir des cliques,
* puis faire l'union de toutes les cliques,
* passer encore au complémentaire.

## Histoire

Les graphes de Turán portent le nom de Pál Turán, qui les a définis et utilisés pour la démonstration du théorème de Turán.

