Independent sets in edge-clique graphs II
classification
🧮 math.CO
cs.DM
keywords
graphsedge-cliqueproblemindependentcographsnp-completeplanarwithout
read the original 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 paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.