Maw-Shang Chang, Ton Kloks, Ching-Hao Liu
Published 2012-06-10Version 1
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.
Comments: arXiv admin note: incorporates arXiv:1205.2483
Independent sets in edge-clique graphs II
On the replica symmetry phase of the independent set problem
The independent set problem is FPT for even-hole-free graphs
![QR code for arXiv:1206.1993 [math.CO]](http://oss.arxitics.com/images/favicon.svg)