Graphe sans triangle
# Graphe sans triangle

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.

## Propriété mathématiques

### Théorie de Ramsey

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

### Propriétés en tant que famille

La famille des graphes sans triangle, contient notamment les graphes acycliques et est contenue dans les graphes sans diamant.

## Reconnaissance

Les graphes sans triangle peuvent être reconnus en temps $O(m^{1,41})$, où $m$ est le nombre d'arêtes.

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 $O(nm)$ (avec $n$ le nombre de sommets) ou en temps $O(n^{\omega }\log(n))$.

Le problème est aussi étudié dans le domaine du test de propriété.

## Coloration

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).

