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. Un graphe acyclique est généralement considéré comme ayant une maille infinie (ou, pour certains auteurs, une maille de -1).

Définition[modifier | modifier le code]

La maille d'un graphe est la longueur du plus court de ses cycles[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. (en) Reinhard Diestel (de), Graph Theory [détail des éditions], 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,‎ .