Independent sets in edge-clique graphs
From MaRDI portal
Publication:6233574
arXiv1206.1993MaRDI QIDQ6233574FDOQ6233574
Ton Kloks, Maw-Shang Chang, Ching-Hao Liu
Publication date: 10 June 2012
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.
This page was built for publication: Independent sets in edge-clique graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6233574)
