Séminaire du LIF
Jeudi 20 novembre à 14h - Luminy, Amphi 12
Stéphane Bessy
Laboratoire LaPCS, Lyon 1
Couverture d'un digraphe fortement connexe en alpha-circuits: une
preuve d'une conjecture de Gallai.
En 1964, Tibor Gallai énonça la conjecture suivante: Tout digraphe D fortement connexe possède une couverture de ses sommets en au plus alpha circuits, où alpha est la stabilité de D. Avec Stéphan Thomassé, nous proposons une preuve de cette conjecture. Les structures combinatoires utilisées dans cette preuve, appelées ordres cycliques, permettent en fait d'établir trois résultats minmax. Un de ces résultats fourni, par ailleurs, une preuve alternative à un résultat d'Adrian Bondy (1976): Tout digraphe fortement connexe possède un circuit de taille supérieure ou égale à son nombre chromatique.
Home page : http://lapcs.univ-lyon1.fr/~bessy/