Loading AI tools
De Wikipédia, l'encyclopédie libre
En théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle.
Le théorème de Mantel, cas particulier du théorème de Turán, est :
Le nombre maximal d'arêtes dans un graphe sans triangle est
La famille des graphes sans triangle, contient notamment les graphes acycliques et est contenue dans les graphes sans diamant.
Les graphes sans triangle peuvent être reconnus en temps , où est le nombre d'arêtes[1].
De façon plus générale, on peut reconnaître les graphes n'ayant pas de cycles d'une certaine longueur (fixé dans l'algorithme), en temps (avec le nombre de sommets)[2] ou en temps [3].
Le problème est aussi étudié dans le domaine du test de propriété[4].
Le théorème de Grötzsch établit que tout graphe planaire sans triangle possède une 3-coloration, selon les définitions de la coloration de graphe.
Le plus petit graphe sans triangle de nombre chromatique supérieur ou égal à 4 est le graphe de Grötzsch (illustration).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.