5
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.