Is there a constant $\alpha>0$ such that every graph $G$ of clique-width $3$ and order $n$ has an induced subgraph of order at least $\alpha n$ and clique-width at most $2$ (in other words, the induced subgraph is a cograph)?

The best upper-bound I currently have on $\alpha$ is $3/5$, given by the cycle on five vertices $C_5$.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.