pith. sign in

arxiv: 1206.5082 · v2 · pith:RK2GTROVnew · submitted 2012-06-22 · 🧮 math.CO · cs.DM

Independent sets in edge-clique graphs II

classification 🧮 math.CO cs.DM
keywords graphsedge-cliqueproblemindependentcographsnp-completeplanarwithout
0
0 comments X
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.