• Title of article

    On facets of stable set polytopes of claw-free graphs with stability number 3

  • Author/Authors

    Pêcher، نويسنده , , Arnaud and Wagler، نويسنده , , Annegret K.، نويسنده ,

  • Issue Information
    روزنامه با شماره پیاپی سال 2010
  • Pages
    6
  • From page
    493
  • To page
    498
  • Abstract
    Obtaining a complete description of the stable set polytopes of claw-free graphs is a long-standing open problem. Eisenbrand et al. recently achieved a breakthrough for the subclass of quasi-line graphs. As a consequence, every non-trivial facet of their stable set polytope has at most two different, but arbitrarily high left hand side coefficients. For the graphs with stability number 2, Cook showed that all their non-trivial facets are 1/2-valued. For claw-free but not quasi-line graphs with stability number at least 4, Stauffer conjectured that the same holds true. In contrast, there are known claw-free graphs with stability number 3 which induce facets with up to eight different left hand side coefficients. We prove that the situation is even worse: for every positive integer b , we exhibit a claw-free graph with stability number 3 inducing a facet with b different left hand side coefficients.
  • Keywords
    stable set polytope , claw-free graph
  • Journal title
    Discrete Mathematics
  • Serial Year
    2010
  • Journal title
    Discrete Mathematics
  • Record number

    1599261