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