Graphs and Optimization

News

  • Coming talks:
    • July, 6th, 10h (MIP conference room): Arnaud Pêcher (IRIT) - From matchings to stable sets of claw-free graphs
      • Abstract: "Providing a complete description of the stable set polytopes of claw-free graphs is a long-standing open problem since almost twenty years. Eisenbrandt et al. recently achieved a breakthrough for the subclass of quasi-line graphs. As a consequence facets of the stable set polytope of quasi-line graphs have at most two left coefficients. For stable set polytopes of claw-free graphs with maximum stable set size at least four, Stauffer conjectured in 2005 that this still holds. I will explain that for claw-free graphs with stability number 3, we have an opposite picture: there are facets with arbitrary many different left coefficients. A linear-program turned out to be the key component to find out these odd facets."

Links

Contacts