Maille (théorie des graphes)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Maille.

En théorie des graphes, la maille d'un graphe est la longueur du plus court de ses cycles[1]. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de -1).

Exemples[modifier | modifier le code]

Familles associées[modifier | modifier le code]

Lien avec la coloration[modifier | modifier le code]

Il existe des théorèmes à propos du rapport entre la maille et le nombre chromatique des graphe. Par exemple un théorème de Paul Erdős, publié en 1959[2],[3] donne que pour tout g et k, il existe un graphe de maille au moins g et de nombre chromatique au moins k. Par exemple, le graphe de Grötzsch a une maille de et un nombre chromatique de 4. Lapreuve de ce théorème utilise la méthode probabiliste.

Notes et références[modifier | modifier le code]

  1. Reinhard Diestel, Graph Theory, Springer, coll. « Graduate Texts in Mathematics » (no 173),‎ , 4e éd., 451 p. (ISBN 978-3-642-14278-9, présentation en ligne), p. 11
  2. Paul Erdős, « Graph theory and probability », Canadian Journal of Mathematics, vol. 11,‎ , p. 34-38 (DOI 10.4153/CJM-1959-003-9).
  3. Frédéric Havet, « Méthode probabiliste pour la coloration de graphes : Graphe de grande maille et de grand nombre chromatique (présentation) », sur Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier,‎ 2009.