Graphe sans 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 ${\displaystyle \lfloor n^{2}/4\rfloor .}$

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 ${\displaystyle O(m^{1,41})}$, où ${\displaystyle m}$ 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 ${\displaystyle O(nm)}$ (avec ${\displaystyle n}$ le nombre de sommets)^[2] ou en temps ${\displaystyle O(n^{\omega }\log(n))}$^[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).