clique width
- 2022/09 Tran2022
- page 26 : modular-width $k$ upper bounds clique width by $\mathcal O(k)$ – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
- page 26 : bounded clique width does not imply bounded modular-width – Proposition 4.6. Modular-width strictly upper bounds Clique-width.
- 2019 Sorge2019
- page 9 : distance to cograph $k$ upper bounds clique width by $2^{\mathcal O(k)}$ – Lemma 4.17. The distance $c$ to a cograph upper bounds the cliquewidth $q$. We have $q \le 2^{3+c}-1$.
- 2012 GanianTwinCover2012
- page 263 : twin-cover number $k$ upper bounds clique width by $\mathcal O(k)$ – The clique-width of graphs of twin-cover $k$ is at most $k+2$.
- 2006 Oum2006
- rank width $k$ implies that clique width is $2^{\mathcal O(k)}$ – Proposition 6.3
- clique width $k$ upper bounds rank width by $\mathcal O(k)$ – Proposition 6.3
- 2000 courcelle2000
- page 18 : treewidth $k$ upper bounds clique width by $2^{\mathcal O(k)}$ – We will prove that for every undirected graph $G$, $cwd(G) \le 2^{twd(G)+1}+1$ …
- https://en.wikipedia.org/wiki/Clique-width
- clique width – … the minimum number of labels needed to construct G by means of the following 4 operations: 1. Creation of a new vertex… 2. Disjoint union of two labeled graphs… 3. Joining by an edge every vertex labeled $i$ to every vertex labeled $j$, where $i \ne j$ 4. Renaming label $i$ to label $j$
- unknown
- distance to cograph $k$ upper bounds clique width by $f(k)$
- linear clique-width $k$ upper bounds clique width by $f(k)$
- clique width $k$ upper bounds boolean width by $\mathcal O(k)$
- boolean width $k$ upper bounds clique width by $2^{\mathcal O(k)}$
- modular-width $k$ upper bounds clique width by $f(k)$
- bounded grid does not imply bounded clique width
- SchroderThesis
- page 16 : bounded clique cover number does not imply bounded clique width – Proposition 3.9
- page 23 : bounded genus does not imply bounded clique width – Proposition 3.17
- page 23 : bounded distance to planar does not imply bounded clique width – Proposition 3.17
- page 28 : bounded maximum degree does not imply bounded clique width – Proposition 3.26
- page 28 : bounded distance to bipartite does not imply bounded clique width – Proposition 3.26
- page 33 : bounded bisection bandwidth does not imply bounded clique width – Proposition 3.32