{
  "id": "1206.1993",
  "version": "v1",
  "published": "2012-06-10T04:02:13.000Z",
  "updated": "2012-06-10T04:02:13.000Z",
  "title": "Independent sets in edge-clique graphs",
  "authors": [
    "Maw-Shang Chang",
    "Ton Kloks",
    "Ching-Hao Liu"
  ],
  "comment": "arXiv admin note: incorporates arXiv:1205.2483",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "We show that the edge-clique graphs of cocktail party graphs have unbounded rankwidth. This, and other observations lead us to conjecture that the edge-clique cover problem is NP-complete for cographs. We show that the independent set problem on edge-clique graphs of cographs and of distance-hereditary graphs can be solved in O(n^4) time. We show that the independent set problem on edge-clique graphs of graphs without odd wheels remains NP-complete.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-06-10T04:02:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "edge-clique graphs",
      "independent set problem",
      "odd wheels remains np-complete",
      "cocktail party graphs",
      "edge-clique cover problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1206.1993C"
    }
  }
}