Graphe sans triangle

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Théorie de Ramsey[modifier | modifier le code]

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[modifier | modifier le code]

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

Reconnaissance[modifier | modifier le code]

Les graphes sans triangle peuvent être reconnus en temps O(m^{1,41}), où 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 O(nm) (avec n le nombre de sommets)[2] ou en temps O(n^{\omega} \log(n))[3].

4-coloration du graphe de Grötzsch.

Coloration[modifier | modifier le code]

Le théorème de Grötzsch (en) établit que tout graphe planaire sans triangle possède une 3-coloration, selon les définition 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[modifier | modifier le code]

  1. Plus précisément en O(m^{2\omega/(\omega + 1)}), où \omega est l'exposant pour la multiplication matricielle, voir (Alon, Yuster et Zwick 1994) et (Alon, Yuster et Zwick 1997)
  2. (en) Burkhard Monien, « How to find long paths efficiently », North-Holland Mathematics Studies, vol. 109,‎ 1985, p. 239 - 254 (lire en ligne)
  3. (en) N. Alon, R. Yuster et U. Zwick, « Color-coding », Journal of the ACM, vol. 42, no 4,‎ 1995, p. 844-856 (lire en ligne)

Bibliographie[modifier | modifier le code]

  • (en) Noga Alon, R. Yuster et U. Zwick, « Finding and counting given length cycles », dans Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands,‎ 1994, p. 354-364.
  • (en) N. Alon, R. Yuster et U. Zwick, « Finding and counting given length cycles », Algorithmica,‎ 1997, p. 354-364 (lire en ligne).
  • (de) Herbert Grötzsch, « Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel », Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, vol. 8,‎ 1959, p. 109 - 120.

Liens externes[modifier | modifier le code]