title: Graphe sans triangle
text: # 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).
  
  