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[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].

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

Coloration[modifier | modifier le code]

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

↑ 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)
↑ (en) Burkhard Monien, « How to find long paths efficiently », North-Holland Mathematics Studies, vol. 109,‎ 1985, p. 239 - 254 (lire en ligne)
↑ (en) N. Alon, R. Yuster et U. Zwick, « Color-coding », Journal of the ACM, vol. 42, n^o 4,‎ 1995, p. 844-856 (lire en ligne)
↑ Noga Alon, Tali Kaufman, Michael Krivelevich et Dana Ron, « Testing Triangle-Freeness in General Graphs », SIAM J. Discrete Math., vol. 22, n^o 2,‎ 2008, p. 786-819 (DOI 10.1137/07067917X)

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]

Les graphes sans triangle sur Information System on Graph Classes and their Inclusions.

[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, n^o 4,‎ 1995, p. 844-856 (lire en ligne)

[4] Noga Alon, Tali Kaufman, Michael Krivelevich et Dana Ron, « Testing Triangle-Freeness in General Graphs », SIAM J. Discrete Math., vol. 22, n^o 2,‎ 2008, p. 786-819 (DOI 10.1137/07067917X)

[1]

[2]

[3]

[4]