1
$\begingroup$

Assume a graph class excludes a certain bicique $K_{n,n}$ and has bounded cliquewidth. Then by a result of Gurski and Wanke, this class also has bounded treewidth. Is there a similar result that states the following: Every graph class with bounded cliquewidth that is monotone (i.e., closed under removing edges and vertices) has bounded treewidth?

$\endgroup$
2
$\begingroup$

Yes, the statement is true. Take a monotone class with bounded cliquewidth. We show that the size of bicliques is bounded. If it were not bounded, we could remove some edges and vertices (by monotonicity) and obtain arbitrarily large subdivided cliques. Thus, it would not have bounded cliquewidth.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.