Mardi 17 Décembre


Retour à la vue des calendrier
Mardi 17 Décembre
Heure: 12:00 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Konig's edge-colouring theorem for all graphs
Description: Denis Cornaz We show that the maximum degree of a
graph G is equal to the minimum number of ocm sets covering G,
where an ocm set is the vertex-disjoint union of elementary odd
cycles and one matching, and a collection of ocm sets covers G if
every edge is in the matching of an ocm set or in some odd cycle
of at least two ocm sets.
This min-max relation gives a linear description of the star
polytope with a minimal TDI-system.
Joint work with V. H. Nguyen from LIP6.