{
  "id": "1612.02670",
  "version": "v1",
  "published": "2016-12-06T16:04:25.000Z",
  "updated": "2016-12-06T16:04:25.000Z",
  "title": "Lovász-Schrijver PSD-operator on Claw-Free Graphs",
  "authors": [
    "Silvia Bianchi",
    "Mariana Escalante",
    "Graciela Nasini",
    "Annegret Wagler"
  ],
  "categories": [
    "math.CO",
    "math.OC"
  ],
  "abstract": "The subject of this work is the study of $\\LS_+$-perfect graphs defined as those graphs $G$ for which the stable set polytope $\\stab(G)$ is achieved in one iteration of Lov\\'asz-Schrijver PSD-operator $\\LS_+$, applied to its edge relaxation $\\estab(G)$. In particular, we look for a polyhedral relaxation of $\\stab(G)$ that coincides with $\\LS_+(\\estab(G))$ and $\\stab(G)$ if and only if $G$ is $\\LS_+$-perfect. An according conjecture has been recently formulated ($\\LS_+$-Perfect Graph Conjecture); here we verify it for the well-studied class of claw-free graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-12-06T16:04:25.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "claw-free graphs",
      "lovász-schrijver psd-operator",
      "perfect graph conjecture",
      "edge relaxation",
      "polyhedral relaxation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}