Independent sets in edge-clique graphs II
From MaRDI portal
Publication:6233882
arXiv1206.5082MaRDI QIDQ6233882FDOQ6233882
Authors: Ching-Hao Liu, Ton Kloks, Sheung-Hung Poon 
Publication date: 22 June 2012
Abstract: We show that 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. We show that the independent set problem on edge-clique graphs of graphs without odd wheels remains NP-complete. We present a PTAS for planar graphs and show that the problem is polynomial for planar graphs without triangle separators.
This page was built for publication: Independent sets in edge-clique graphs II
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6233882)
