<p>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.</p>

CC BY-SA 4.0
2021-06-23T09:06:24.157Z
2021-06-23T09:06:24.157Z
Jan
<p>Assume a graph class excludes a certain bicique <span class="math-container">$K_{n,n}$</span> 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 <em>monotone</em>  (i.e., closed under removing edges and vertices) has bounded treewidth?</p>

<treewidth><graph-classes><monotone><cliquewidth>
Treewidth of monotone graph classes with bounded cliquewidth
Jan
# Treewidth of monotone graph classes with bounded cliquewidth

(Asked by: username_0 on 2021-06-23)

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?

**Tags:** treewidth, graph-classes, monotone, cliquewidth

---

## 1 answers

### Answer by username_0 on 2021-06-23. Score: 2

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.


---

