Graphe de Turán

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le graphe de Turan (13,4)

Un graphe de Turán (noté T(n,r)), aussi appelé maximally saturated graph, est un objet de la théorie des graphes.

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.

Ils 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[1].

Propriétés[modifier | modifier le code]

Le nombre chromatique du graphe T(n,r) est r[2]

Notes et références[modifier | modifier le code]

  1. Paul Turán, « On an extremal problem in graph theory », Matematikai és Fizikai Lapok, vol. 48,‎ 1941, p. 436–452
  2. Chong-Yun Chao et George A Novacky Jr, « On maximally saturated graphs », Discrete Mathematics, Elsevier, vol. 41, no 2,‎ 1982, p. 139-143

Voir aussi[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Théorème d'Erdős-Stone (en)

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Turán Graph », MathWorld