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 :
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ù est le nombre d'arêtesPlus précisément en , où est l'exposant pour la multiplication matricielle, voir et .
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) ou en temps .
thumb|4-coloration du graphe de Grötzsch.
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).
Notes et références
Bibliographie . . .
Liens externes Les graphes sans triangle sur Information System on Graph Classes and their Inclusions.
Catégorie:Famille de graphes